[BOJ20437/Java] 문자열 게임 2

1. 문제 요약

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

20437번: 문자열 게임 2

어떤 알파벳 문자가 정확히 K개가 포함된 문자열에 대하여... 그 길이가 최소인 것과 최대인 것을 찾는 것이다.

문제에서 4번 단계에서는 시작과 끝이 해당 문자이면서 K개를 포함하는 경우를 찾는데,

3번 단계에서는 따로 그런 설명이 없다. 근데 똑같은 문제임.. 길이가 최소인 것을 찾으려면 어쨌든 시작과 끝이 해당 문자이면서 K개를 포함하고 있을것! 그렇다면 우리는 문자가 언제 K개가 포함되는지 알아보면 된다.

 

2. 입출력

3. 접근 아이디어

알파벳 위치와 개수를 어떻게 효율적으로 접근하면서 관리할 수 있을까?

-> 알파벳 위치를 다루는 이차원 배열과 알파벳 개수를 다루는 배열을 하나씩 생성해서 관리

(ArrayList를 통해서 관리해도 될 것 같음, 그러면 굳이 2개로 나눠서 할 필요 없이 size함수 호출로 관리할 수 있을 것)

 

정확히 K개의 알파벳이 포함되어 있는 문자열을 어떻게 찾을까?

-> 알파벳 개수가 K개일 때 위치 배열의 제일 첫 위치와 지금 위치를 비교한다면 문자열을 찾아 길이를 구할 수 있음

 

내가 지금까지 살펴본 문자열에서 어떤 한 문자가 K개보다 많은 수가 포함되어 있다면 어떻게 하면 좋을까?

-> 만약 어떤 문자가 K+2개가 있다면 나는 첫번째가 아닌 2번째부터 문자열을 시작한다면 또 정확히 문자가 K개 포함된 문자열을 찾을 수 있음

 

4. 작성 코드

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

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {
			char[] arr = br.readLine().toCharArray();
			int k = Integer.parseInt(br.readLine());
            // 알파벳 각각이 어디에 있는지를 저장하는 배열
			int[][] location = new int[26][10001];
            // 알파벳이 몇개 있는지 저장하는 배열
			int[] count = new int[26];
            //초기 값 설정
			int ans3 = 100001, ans4 = 0;
			for(int i = 0; i<arr.length; i++) {
				int t = arr[i]-'a';
				count[t]++;
				location[t][count[t]]=i;
				if(count[t] >= k) {
					int l = location[t][count[t]] - location[t][count[t]-k+1]+1;
					if(l < ans3) ans3 = l;
					if(l > ans4) ans4 = l;
				}
			}
			if(ans3 == 100001 || ans4 == 0) {
				sb.append(-1).append('\n');
			}
			else {
				sb.append(ans3).append(' ').append(ans4).append('\n');
			}
		}
		System.out.println(sb);
	}

}