백준 10465 자바 - Rolling Encryption (BOJ 10465 JAVA)

문제 : boj10465

 

 

1.

  우선 문자열에서 k개를 그대로 출력한다. 이후 각 character마다 그 이전 k개의 문자열 중 가장 많이 나온 문자를 찾는다. 그리고 가장 많이 나온 문자(동일한 수가 나온게 있다면 알파벳에서 먼저 나오는걸로)만큼 쉬프트 시킨다(a면 1번, b면 2번, ..., z면 26번)

 

2.

  문제만 보면 간단히 구할 수 있을 것 같은데, 문제는 k가 최대 10000이고 문자열의 길이가 최대 100000이므로 단순하게 각 character마다 이전 k개를 보게된다면 O(10000 * 100000)이 필요하므로 시간초과가 나게 된다.

 

  이 경우 소문자는 총 26개이므로 별도 배열로 각 문자에 대해 세보면 더 효율적으로 가장 많이 나온 문자를 찾을 수 있다.

 

  "abbaabbac"에 대해 k=5라면 우선 처음 5개는 그냥 출력하면 된다. 출력하면서 a~z 까지에 대해 카운팅한다. 그럼 O(26)으로 가장 많이 나온 문자를 찾을 수 있다(동일 카운팅에 대해서는 변경하지 않으면 동일 카운팅에 대해 알파벳순으로 가장 빠른 문자도 찾을 수 있다.)

 

  그리고 다음 character를 볼 때는 그 이전 k개를 모두 세는게 아니고 다음과 같이 범위가 이동했다고 보면 이전 범위의 가장 왼쪽을 cnt에서 -1하고, 현재 character를 cnt에서 +1 해주면 된다. 최종적으로 O(26 * 100000)으로 구할 수 있다.

 

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private char getShiftedChar(char c, int[] cnt) {
        int maxCnt = 0;
        int maxIdx = 0;

        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] > maxCnt) {
                maxCnt = cnt[i];
                maxIdx = i;
            }
        }

        int charNum = c-'a'+maxIdx+1;
        charNum %= 26;

        return (char)('a'+charNum);
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        String s = br.readLine();
        if (s.length() <= k) {
            System.out.println(s);
            return;
        }

        StringBuilder answer = new StringBuilder();
        int[] cnt = new int['z'-'a'+1];
        for (int i = 0; i < k; i++) {
            cnt[s.charAt(i)-'a']++;
            answer.append(s.charAt(i));
        }

        for (int i = k; i < s.length(); i++) {
            answer.append(getShiftedChar(s.charAt(i), cnt));
            cnt[s.charAt(i-k)-'a']--;
            cnt[s.charAt(i)-'a']++;
        }

        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}