[백준_20437번] 문자열 게임 2

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) 

 

[코드]

import java.util.*;

public class BaekJoon_20437 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		
		while(t-->0) {
			String w=sc.next();
			int k=sc.nextInt();
			
			if(k==1) { // 해주지 않으면 시간초과 
				System.out.println("1 1");
				continue;
			}
			
			int[] alpabet=new int[26];
			for(int i=0;i<w.length();i++)
				alpabet[w.charAt(i)-'a']++;
			
			int min=Integer.MAX_VALUE; // 3번의 답
			int max=Integer.MIN_VALUE; // 4번의 답
			for(int i=0;i<w.length();i++) {
				// 문자열 w에서 k개 이하로 포함된 문자 x는 탐색할 이유가 없음 
				if(alpabet[w.charAt(i)-'a']<k) 
					continue;
				
				// 문자열 w에서 k개 이상 포함된 문자 x -> 조건에 만족하는 문자열 찾기
				int count=0;
				for(int j=i;j<w.length();j++) {
					if(w.charAt(i)==w.charAt(j))
						count++;
					
					// 부분 문자열에서 문자 x가 k개 포함될 때  
					if(count==k) {
						min=Math.min(min, j-i+1); // 3번의 답 -> 가장 짧은 문자열 길이
						
						if(w.charAt(i)==w.charAt(j))
							max=Math.max(max,j-i+1); // 4번의 답 -> 가장 긴 문자열 길이
					    
						break; // 없으면 시간초과
					}
				}
			}
			
			if(min==Integer.MAX_VALUE||max==Integer.MIN_VALUE)
				System.out.println(-1);
			else
				System.out.println(min+" "+max);
		}
	}
}

 

[고찰]

 해당 문제는 슬라이딩 윈도우 문제였다. 일단 이번 문제를 풀 때 주의해야 할 점은 시간초과 부분이었다. k가 1인 경우 처리와 for문의 break를 걸어주지 않으면 시간초과를 받기 때문에 주의해야 한다. 

 또한, 문제 해결 방법의 핵심은 문자열의 각 알파벳의 등장 횟수를 저장하는 배열을 선언하는 것이다. 해당 배열을 사용하여 문자열을 처음부터 탐색하면서 k번 이상 나오는 문자를 중심으로 문제 3번과 4번의 대한 해답을 구하면 된다. 이때, 슬라이딩 윈도우 알고리즘을 사용하여 해결해야 한다.