[Java] 백준 20437번: 문자열 게임 2

[문제 바로 가기] - 문자열 게임 2

💡 접근 방식

두 게임 모두 슬라이딩 윈도우를 사용하여 푸는 것은 알아냈다. 풀이까지 했으나 시간초과가 나서(답이 맞는지는 모르겠다) 풀이를 참고했다 (ㅜㅜ)

먼저 문자열 W에 있는 알파벳을 모두 카운트해서 alphabet 배열에 저장한다. 그리고 W의 길이만큼 반복문을 돌며 해당 자리의 알파벳이 K개 이하라면 넘어간다. i번째와 j번째 알파벳이 같다면 count++ 해주고 count가 K라면 min과 max를 갱신해준다.

어찌보면 슬라이딩 윈도우보다는 투포인터에 가까운 것 같다. 두 게임을 한번에 계산하는 것이 시간초과가 나지 않는 포인트인 것 같다.

처음 풀이

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

/**
 * 백준 20437번 문자열 게임 2
 */

public 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());
		
		for (int i = 0; i < T; i++) {
			String W = br.readLine();
			int K = Integer.parseInt(br.readLine());
			
			int first = first(W, K);
			int second = second(W, K);
			
			if (first == -1 || second == -1) System.out.println(-1);
			else System.out.println(first + " " + second);
		}	
	}
	
	// 슬라이딩 윈도우 : K개부터 시작
	public static int first(String W, int K) {
		int len = K - 1;
		
		int start = 0;
		int end = K - 1;
		int min = Integer.MAX_VALUE;
		boolean isInclude = false;
		
		while (!isInclude && end - start < W.length()) {
			int alphabet[] = new int[30];
			for (int i = start; i <= end; i++) {
				alphabet[W.charAt(i) - 97]++;
				
				if (alphabet[W.charAt(i) - 97] == K) {
					min = Math.min(min, end - start + 1);
					return min;
				}
			}
			
			while (end + 1 < W.length()) {
				if (alphabet[W.charAt(end) - 97] == K) {
					min = Math.min(min, end - start + 1);
					isInclude = true;
					break;
				}
				
				alphabet[W.charAt(start++) - 97]--;
				alphabet[W.charAt(++end) - 97]++;
			}
			
			len++;
			start = 0;
			end = len;
		}
		
		if (min == Integer.MAX_VALUE) return -1;
		return min;
	}
	
	public static int second(String W, int K) {
		int len = W.length() - 1;
		
		int start = 0;
		int end = W.length() - 1;
		int max = Integer.MIN_VALUE;
		boolean isInclude = false;

		while (!isInclude && end - start + 1 >= K) {
			int alphabet[] = new int[30];
			
			for (int i = start; i <= end; i++) {
				alphabet[W.charAt(i) - 97]++;
			}
			
			while (end + 1 < W.length()) {
				if (alphabet[W.charAt(end) - 97] == K && W.charAt(start) == W.charAt(end)) {
					max = Math.max(max, end - start + 1);
					isInclude = true;
					break;
				}
				
				alphabet[W.charAt(start++) - 97]--;
				alphabet[W.charAt(++end) - 97]++;
			}
			
			len--;
			start = 0;
			end = len;
		}
		
		if (max == Integer.MIN_VALUE) return -1;
		return max;
	}
}

맞은 풀이

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

/**
 * 백준 20437번 문자열 게임 2
 */

public 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());
		
		for (int t = 0; t < T; t++) {
			String W = br.readLine();
			int K = Integer.parseInt(br.readLine());

			if (K == 1) {
				System.out.println("1 1");
				continue;
			}
			
			int[] alphabet = new int[26];
			
			for (int i = 0; i < W.length(); i++) {
				alphabet[W.charAt(i) - 97]++;
			}
			
			int min = Integer.MAX_VALUE;
			int max = -1;
			
			for (int i = 0; i < W.length(); i++) {
				if (alphabet[W.charAt(i) - 97] < K) continue;
				
				int count = 1;
				
				for (int j = i + 1; j < W.length(); j++) {
					if (W.charAt(i) == W.charAt(j)) count++;
					
					if (count == K) {
						min = Math.min(min, j - i + 1);
						max = Math.max(max, j - i + 1);
						break;
					}
				}
			}
			
			if (max == -1 || min == Integer.MAX_VALUE) System.out.println(-1);
			else System.out.println(min + " " + max);
		}	
	}
}