백준 20437 - 문자열 게임 2

문제

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

풀이

초반에 너무 복잡한 방식으로 접근하여 애를 먹었던 문제였다. 결국 문제에서 주어진 조건을 만족하는 문자열은 특정 문자를 $K$개만 포함한다. 이 조건에 집중하여 다음 전개로 로직을 구성하였다.

1. 먼저 입력받은 문자열내 문자들의 개수를 카운팅하여 저장한다.
2. 문자열의 첫 문자부터 탐색을 시작한다. 문자열내 문자가 $K$개이상 존재할 경우만 탐색한다.
3. 해당 문자이후의 문자열을 대상으로 특정 문자의 개수를 카운팅한다. $K$개를 충족할 경우 최소 길이, 최대 길이를 갱신해준다. 문자열 양 끝 문자가 특정 문자와 같아야 하는 조건도 카운팅 직후 $K$와 일치할 경우 길이를 갱신하기에 함께 충족시킬 수 있다.

$K$개 이상 포함된 문자들만을 대상으로 문자열 내에서 탐색을 진행하기 때문에 실질적인 로직의 시간 복잡도는 $O(W)$로 수렴한다. 따라서 $W=10000$인 최악의 경우에도 무난히 1초의 제한 조건을 통과할 수 있다.

코드

import static java.lang.Integer.*;

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

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

		while (T-- > 0) {
			String line = br.readLine();
			int K = parseInt(br.readLine());

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

			int[] alphabet = new int[26];
			line.chars()
				.forEach(c -> alphabet[c - 'a']++);

			int minLength = MAX_VALUE;
			int maxLength = MIN_VALUE;

			for (int i = 0; i < line.length(); i++) {
				char letter = line.charAt(i);
				if (alphabet[letter - 'a'] < K)
					continue;

				int count = 1;
				for (int j = i + 1; j < line.length(); j++) {
					if (line.charAt(j) != letter)
						continue;

					count++;

					if (count == K) {
						minLength = Math.min(minLength, j - i + 1);
						maxLength = Math.max(maxLength, j - i + 1);
						break;
					}
				}
			}

			if (minLength == MAX_VALUE || maxLength == MIN_VALUE) {
				sb.append("-1").append("\n");
				continue;
			}

			sb.append(minLength)
				.append(" ")
				.append(maxLength)
				.append("\n");
		}

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

결과