백준 골드5 문자열 게임2

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

---

처음에 봤을 때 어떻게 풀어야할지 감이 안왔다.
그래서 map 두개 써서 저장도 해보고...
이리저리 하다가 슬라이싱 윈도우 문제인 것을 알았고
3번은 양 끝이 같은 최소 길이, 4번은 양 끝이 같은 최대 길이라는 것을 알았다.
이에 따라 아래와 같이 구현하였다.

양 끝이 같으면 슬라이싱 윈도우의 범위 안의 문자를 모두 탐색한다.
하지만 시간 초과가 났다.

---

시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;

public class Main {
    private static int K, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, size;
    private static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bufferedReader.readLine());
        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < T; i++) {
            flag = false;
            String str = bufferedReader.readLine();
            K = Integer.parseInt(bufferedReader.readLine());
            String arr[] = str.split("");
            size = K;
            method(0, size, arr);

            if (flag) {
                stringBuilder.append(min).append(" ").append(max).append("\n");
            } else {
                stringBuilder.append("-1").append("\n");
            }
        }
        System.out.println(stringBuilder);
    }

    private static void method(int start, int end, String arr[]) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        if (arr[start].equals(arr[end - 1])) {
            //양끝이 같을 때 탐색 시작
            int count = 2;

            for (int i = start + 1; i < end - 1; i++) {
                if (arr[i].equals(arr[start])) {
                    count++;
                }
            }
            if (count == K) {
                min = Math.min(size, min);
                max = Math.max(size, max);
                flag = true;
            }
        }

        if (start == 0 && end == arr.length) { //모두 탐색됨
            return;
        } else if (end == arr.length) { //폭을 늘려야 할 때
            method(0, ++size, arr);
        } else { //슬라이싱 윈도우
            method(++start, ++end, arr);
        }
    }
}

시간이 오래 걸리는 이유는 알았는데
어떻게 바꿔야 할지 고민이었다.
풀이를 찾아본 결과 어차피 소문자 알파벳으로 이루어져 있으니 알파벳 개수를 하나씩 세서 배열에 저장하고 알파벳 개수가 k보다 작으면 탐색조차 안하는 것이다.

하지만 그렇게 구현하고도 1퍼대에서 시간 초과가 났으니...
왜그런가 하고 봤더니 count가 K가 되면 탐색을 중지해야한다.
break를 안써서 count가 K가 되어도 계속 탐색하고 있던 것.
계속 탐색해서 같은 문자를 만나도 그 문자열은 같은 문자가 K+1개 이상인 것이기 때문에 정답이 아니다.

---

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bufferedReader.readLine());
        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < T; i++) {
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            int alpha[] = new int[26];
            boolean flag = false;
            String str = bufferedReader.readLine();
            int K = Integer.parseInt(bufferedReader.readLine());

            if(K == 1){
                stringBuilder.append("1 1\n");
                continue;
            }

            for (int j = 0; j < str.length(); j++) {
                alpha[str.charAt(j) - 'a']++;
            }

            for (int j = 0; j < str.length(); j++) {
                char ch = str.charAt(j);

                if (alpha[ch - 'a'] < K) {
                    continue;
                }
                int count = 1;

                for (int m = j + 1; m < str.length(); m++) {
                    if (str.charAt(j) == str.charAt(m)) {
                        count++;
                        if (count == K) {
                            min = Math.min(min, m - j + 1);
                            max = Math.max(max, m - j + 1);
                            flag = true;
                            break; //이거 써야 시간초과 안남
                        }
                    }
                }
            }

            if (flag) {
                stringBuilder.append(min).append(" ").append(max).append("\n");
            } else {
                stringBuilder.append("-1").append("\n");
            }
        }
        System.out.println(stringBuilder);
    }

}