BOJ_20437_문자열 게임 2 (Java)

[Gold V] 문자열 게임 2 - 20437

문제 링크

성능 요약

메모리: 28544 KB, 시간: 296 ms

분류

슬라이딩 윈도우, 문자열

제출 일자

2025년 3월 18일 05:00:29

문제 설명

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

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번 답 구하기를 각각 나누어서 설명하겠다.

1. 가장 짧은 문자열: 투 포인터 (슬라이딩 윈도우) 방식

• 왼쪽(left)과 오른쪽(right) 포인터를 사용하여 윈도우를 조절
• 윈도우 내에서 각 문자의 발생 횟수를 계산
• 어떤 문자가 정확히 K번 등장하면 최소 길이를 갱신하고 윈도우를 축소

2. 가장 긴 문자열: Deque 활용

• 각 알파벳별로 Deque를 사용하여 최대 K개의 인덱스를 추적
• 모든 문자에 대해, 정확히 K개의 해당 문자를 포함하는 가장 긴 부분 문자열을 찾음
• 첫 번째와 마지막 글자가 같은 문자이므로, 자연스럽게 조건 충족됨

코드

package BOJ_20437_문자열게임;
        
/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int T, K;
    static String W;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_20437_문자열게임/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            W = br.readLine();
            K = Integer.parseInt(br.readLine());

            // 문자열별 개수
            int[] count = new int[26];
            for(int i=0; i<W.length(); i++) {
                count[W.charAt(i) - 'a']++;
            }

            // K개짜리 정답 존재
            boolean flag = false;
            for(int i=0; i<26; i++) {
                if(count[i] >= K) {
                    flag = true;
                    break;
                }
            }

            if(!flag){
                sb.append("-1").append("\n");
                continue;
            }

            // 1번 답구하기
            int minLen = Integer.MAX_VALUE;
            int left=0, right = 0;
            int[] charCount = new int[26];

            while(right < W.length()) {
                char curr = W.charAt(right);
                charCount[curr - 'a']++;

                while(charCount[curr - 'a'] >= K) {
                    if(charCount[curr - 'a'] == K) {
                        minLen = Math.min(minLen, right-left+1);
                    }

                    charCount[W.charAt(left) - 'a']--;
                    left++;
                }

                right++;
            }

            // 2번답 구하기
            int maxLen = -1;
            Deque<Integer>[] K_len = new ArrayDeque[26];
            for(int i=0; i<26; i++) {
                K_len[i] = new ArrayDeque<>();
            }

            for(int i=0; i<W.length(); i++) {
                int curr = W.charAt(i)-'a';
                K_len[curr].add(i);

                if(K_len[curr].size() > K){
                    K_len[curr].pollFirst();
                }

                if(K_len[curr].size() == K){
                    int first = K_len[curr].peekFirst();
                    int last = K_len[curr].peekLast();
                    maxLen = Math.max(maxLen, last - first + 1);
                }
            }

            if(minLen == Integer.MAX_VALUE) sb.append("-1").append("\n");
            else sb.append(minLen).append(" ").append(maxLen).append("\n");
        }


        System.out.println(sb.toString());
        br.close();
    }
}