[백준 20437] 문자열 게임 2 - JAVA

문제

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

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

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

입력

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

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

출력

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

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

---

접근 방법

부분 문자열에서 특정 문자가 정확히 $K$개인 것 중 길이의 최소와 최대를 동시에 구하는 문제입니다.

처음 생각한 것은 두 개의 최소와 최대에 대한 두 개의 투 포인터 메서드를 구현하자는 생각이었지만 그렇게 조잡하게 문제를 제출하지 않았을 것이고 다른 방법과 의도가 있을 것이라고 생각했습니다.

그래서 정답을 정해놓지 않고 순차적으로 할 수 있는 것들을 해나갔습니다.

부분 문자열에서 특정 문자가 $K$개가 되는지를 확인하려면 알파벳을 계수 정렬 방식으로 카운팅을 해야겠다는 생각을 먼저 하게 되었고 alphabet이라는 정수형 배열을 선언합니다.

그리고 난 후 한 번의 $for$문을 돌리면서 alphabet[spelling[i] - 97]++ 연산을 수행했습니다.

• 우선 spelling 배열은 문자열을 char[] 배열로 문자 단위로 나눈 배열입니다.
• spelling[i] - 97은 '문자열과 숫자'의 연산으로 spelling[i]가 연산을 위해 int 타입의 아스키 코드 값으로 자동 타입캐스팅 해서 연산을 수행합니다.
  • spelling[i] 에 들어올 수 있는 것은 소문자 알파벳이고 소문자 알파벳 'a'의 아스키 코드값은 97이므로 97을 빼주게 됩니다.
  • 이렇게 하면 'a' - 97 = 0이 되고 'z' - 97 = 25가 됩니다.
  • 즉 알파벳의 개수를 카운팅 하는 alphabet 배열에서 특정 문자의 인덱스가 되는 셈입니다.
  • alphabet[spelling[i] - 97]++은 문자열에서 i번 째 위치한 문자의 counting을 1 증가 시키는 것입니다.

이후 alphabet 배열을 확인해보니 각 알파벳의 출현 개수가 $K$를 넘지 않는 알파벳이 많은 것을 알 수 있었고

그러면 알파벳 단위로 최댓값, 최솟값을 구하는 로직을 구현하자는 생각을 하게 되었습니다.

• 이후에는 각 알파벳 별로 출현 인덱스를 배열로 저장하고 부분 문자열에서 특정 문자가 정확히 K개 나오는 케이스를 찾기 위해 슬라이딩 윈도우를 활용해서 문제를 풀었습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            char[] spellings = br.readLine().toCharArray();
            int K = Integer.parseInt(br.readLine());

            startGame(spellings, K, sb);
        }
        System.out.println(sb);
    }

    static void startGame(char[] spellings, int K, StringBuilder sb) {
        int L = spellings.length;
        int[] alphabet = new int[26];

        for (char c : spellings) {
            alphabet[c - 97]++;
        }

        int min = L + 1;
        int max = -1;

        for (int i = 0; i < 26; i++) {
            if (alphabet[i] < K) continue;

            char target = (char)(i + 97);
            int[] memo = new int[alphabet[i]];
            int index = 0;

            for (int end = 0; end < L; end++) {
                if (spellings[end] == target) {
                    memo[index] = end;
                    index++;
                }
            }

            for (int start = 0; start <= alphabet[i] - K; start++) {
                int end = K + start - 1;

                int currentLength = memo[end] - memo[start] + 1;

                min = Math.min(min, currentLength);
                max = Math.max(max, currentLength);
            }
        }

        if (min == L + 1 || max == -1) sb.append("-1");
        else sb.append(min).append(" ").append(max);
        sb.append("\n");
    }
}