BOJ 20437 문자열 게임 2

https://www.acmicpc.net/problem/20437

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

---

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)

다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000)

---

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.

만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

---

예제 입력 1

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

예제 출력 1

4 8
-1

예제 입력 2

1
abaaaba
3

예제 출력 2

3 4

---

코드

문제에서 나온 3번 조건을 살펴보자. 어떤 문자를 K개 포함하는 가장 짧은 연속 문자열은 양 끝이 같은 문자일 수 밖에 없다.

예를 들면, aabcad 문자열에서 a를 3개 포함하는 문자열이 aabca 인데, 맨 뒤에 굳이 d를 붙여 문자열의 길이를 길게 할 필요가 없다는 말이다.

즉, 3, 4번 조건을 다음과 같이 표현할 수 있을 것이다.

3번 - 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 짧은 연속 문자열의 길이를 구한다.

4번 - 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

대략적인 풀이 과정은 다음과 같다.

1. 각 알파벳마다 문자열 W에서 해당 알파벳이 위치하는 인덱스들을 저장할 덱을 만든다.
2. 문자열 W의 각 문자를 순회하며 해당 문자의 인덱스를 덱에 넣는다.
3. 해당 알파벳의 덱의 size가 K가 되면, 덱의 양 끝에 저장된 인덱스의 차를 이용해 문자열의 길이를 계산한다.
4. 계산한 문자열의 길이 중 가장 긴 길이와 가장 짧은 길이를 구해 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            char[] W = br.readLine().toCharArray();
            int K = Integer.parseInt(br.readLine());

            // K가 1일 경우, 3번과 4번에서 구한 연속 문자열의 길이는 무조건 1, 1이다.
            if(K == 1) {
                answer.append("1 1\n");
                continue;
            }

            int min = Integer.MAX_VALUE; // 3번 조건을 만족시킬 문자열 길이
            int max = Integer.MIN_VALUE; // 4번 조건을 만족시킬 문자열 길이

            // 각 알파벳마다 인덱스들을 저장할 덱을 초기화 시킴
            Deque<Integer>[] alphabets = new Deque[26];
            for (int j = 0; j < 26; j++) {
                alphabets[j] = new ArrayDeque<>();
            }
            
            for (int j = 0; j < W.length; j++) {
                // 검사 중인 인덱스를 해당하는 알파벳 덱에 offer
                int check = W[j] - 'a';
                alphabets[check].offer(j);

                /**
                 * 해당 알파벳 덱의 크기가 K가 되었으면
                 * 덱의 양 끝에 저장된 인덱스의 차를 이용해 문자열의 길이를 계산
                 */
                if(alphabets[check].size() == K) {
                    int length = j - alphabets[check].poll();
                    min = Integer.min(min, length);
                    max = Integer.max(max, length);
                }
            }

            // 가장 긴 문자열의 길이와 가장 짧은 문자열의 길이를 계산
            if(min != Integer.MAX_VALUE && max != Integer.MIN_VALUE) {
                answer.append(min + 1).append(' ').append(max + 1).append('\n');
            } else {
                answer.append(-1).append('\n');
            }
        }

        System.out.println(answer);
    }
}