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

날짜	분류	번호	알고리즘 분류
21-01-17	BOJ	20437	슬라이딩 윈도우	링크

문제 요약

1. 주어진 문자열에서 어떤 문자를 정확히 K개만 포함하는 sub 문자열 중 최단 길이와 최장 길이를 구함

 

풀이

1. 26개의 리스트를 만들어서 각 문자에 해당하는 문자들의 위치를 저장
2. 각 문자별로 x번째 문자와 x+n-1번째 문자의 길이를 계산하여 최대값과 최소값을 비교

 

비고

• 가볍게 풀기 좋은 문제

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder answer = new StringBuilder();

		for (int i = 0; i < T; i++) {
			String str = br.readLine();
			int n = Integer.parseInt(br.readLine());

			List<Integer>[] list = new ArrayList[26];
			for (int j = 0; j < list.length; j++) {
				list[j] = new ArrayList<>();
			}

			for (int j = 0; j < str.length(); j++) {
				char cur = str.charAt(j);
				list[cur - 'a'].add(j);
			}

			int min = Integer.MAX_VALUE;
			int max = Integer.MIN_VALUE;
			for (int j = 0; j < 26; j++) {
				if (list[j].size() < n)
					continue;
				for (int k = 0; k <= list[j].size() - n; k++) {
					int cur = list[j].get(k + n - 1) - list[j].get(k) + 1;
					min = Math.min(min, cur);
					max = Math.max(max, cur);
				}
			}

			if (min == Integer.MAX_VALUE && max == Integer.MIN_VALUE)
				answer.append("-1\n");
			else
				answer.append(min + " " + max + "\n");

		}
		System.out.println(answer);
	}

}