[백준]20437: 문자열 게임2(java)

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

20437번: 문자열 게임 2

문제

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

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

첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다.

두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다.

 

---

풀이

문제 자체는 어렵지 않았지만 어떻게 접근하느냐에 따라 시간이 정말 많이 차이났다.

a~z를 0~25로 표현하여 int형 배열을 만든 후 각 단어의 등장 횟수를 저장한다.

1) 현재 문자가 총 등장 횟수가 K보다 작으면 볼 필요가 없다.

2) 이미 본 단어는 빼준다.

이 2개가 핵심으로 작용했던 것 같다.

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class BJ_G5_20437_문자열게임2 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder ans = new StringBuilder();
        int TC = Integer.parseInt(br.readLine());

        for(int t=1; t<=TC; t++) {
            char[] arr = br.readLine().toCharArray();
            int[]charArr = new int[26];
            int K = Integer.parseInt(br.readLine());
            if(K==1) {
                ans.append("1 1");
                if(t!=TC) {
                    ans.append("\n");
                }
                continue;
            }
            for(int i=0; i<arr.length; i++) {
                charArr[arr[i]-'a']++;
            }
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int i=0; i<arr.length-K+1; i++) {
                char word = arr[i];
                if(charArr[word-'a'] <K) continue;
                int cnt = 1;
                for(int j=i+1; j<arr.length; j++) {
                    if(word == arr[j]) {
                        cnt++;
                    }
                    if(cnt == K) {
                        if(min > j-i+1) {
                            min = j-i+1;
                        }
                        if(max < j-i+1) {
                            max = j-i+1;
                        }
                        charArr[word-'a']--;
                        break;
                    }
                }
            }
            if(min==Integer.MAX_VALUE) {
                ans.append("-1");
            } else {
                ans.append(min + " " + max);
            }
            if(t!=TC) {
                ans.append("\n");
            }
        }
        System.out.printf("%s", ans.toString());
    }
}