백준 20437 문자열 게임2

문제

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

---

입출력

---

예제

---

태그

• 문자열
• 슬라이딩 윈도우

---

풀이

• 주어진 문자열의 첫 글자부터 그 뒤의 글자들을 비교하면 이중 for문으로 시간 초과가 난다.

• 먼저 문자열을 구성하고 있는 알파벳들이 몇 개씩 있는지 확인하고 배열에 그 개수를 담는다.

• 주어진 K개보다 알파벳 개수가 적다면 그 알파벳을 기준으로 탐색하지 않는다.

• continue, break를 적절히 사용하여야 한다.

• continue : 해당 반복문으로 다시 돌아감

• break : 해당 반복문 종료

• K=1 : 최소, 최대는 모두 1이다. 그리고 전체 테스트케이스 반복문으로 돌아간다.(continue)

---

코드

정답 코드

/**
 * 20437_문자열 게임 2
 * 
 * 문자열을 구성하는 알파벳의 개수를 먼저 센다.
 * 알파벳의 개수가 K보다 작으면 해당 알파벳을 기준으로 한 탐색은 넘어간다.
 */

public class P_20437 {
    static int T; // 전체 테스트케이스

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

        for (int tc = 0; tc < T; tc++) {
            int[] alphabet = new int[26]; // 문자열을 구성하는 알파벳의 개수를 세는 배열
            String str = br.readLine();
            int K = Integer.parseInt(br.readLine());

            // 문자열을 구성하는 알파벳의 개수를 담는다.
            for (int i = 0; i < str.length(); i++) {
                alphabet[str.charAt(i) - 'a']++;
            }

            int min = Integer.MAX_VALUE; // 최소 답
            int max = Integer.MIN_VALUE; // 최대 답

            // 문자열을 시작하는 알파벳부터 탐색 시작
            for (int i = 0; i < str.length(); i++) {
                // 해당 알파벳이 총 개수가 K보다 작으면 넘어간다.
                if (alphabet[str.charAt(i) - 'a'] < K){
                    continue;
                }
                
                int cnt = 1; // 알파벳의 개수(K와 비교)

                // 탐색할 알파벳 그 다음 알파벳부터 하나씩 비교해가며 답을 도출한다.
                for (int j = i+1; j < str.length(); j++) {
                    if (str.charAt(i) == str.charAt(j)) {
                        cnt++;
                    }
                    if (cnt == K) {
                        min = Math.min(min, (j-i+1));
                        max = Math.max(max, (j-i+1));
                        break;
                    }
                }
            }

            // K가 1이면 최소, 최대 모두 답은 1
            if (K == 1){
                System.out.println("1 1");
                continue;
            }

            // 만족하는 조건이 없으면
            if (min == Integer.MAX_VALUE || max == Integer.MIN_VALUE){
                System.out.println(-1);
            }
            else{
                System.out.println(min + " " + max);
            }
        }
    }
}