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

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

난이도

골드5

문제

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 정수 K가 주어진다.
3. 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

입력

문자열 게임의 수 T가 주어진다. (1 ≤ T ≤ 100)
다음 줄부터 2개의 줄 동안 문자열 W와 정수 K가 주어진다. (1 ≤ K ≤ |W| ≤ 10,000)

출력

T개의 줄 동안 문자열 게임의 3번과 4번에서 구한 연속 문자열의 길이를 공백을 사이에 두고 출력한다.
만약 만족하는 연속 문자열이 없을 시 -1을 출력한다.

내 코드

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

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

		for (int tc = 0; tc < T; tc++) {
			String W = br.readLine();
			int K = Integer.parseInt(br.readLine());

			HashMap<Character, List<Integer>> hm = new HashMap<>();
			for (int i = 0; i < W.length(); i++) {
				char c = W.charAt(i);
				hm.putIfAbsent(c, new ArrayList<>());
				hm.get(c).add(i);
			}

			int minLen = Integer.MAX_VALUE;
			int maxLen = Integer.MIN_VALUE;

			for (HashMap.Entry<Character, List<Integer>> entry : hm.entrySet()) {
				List<Integer> list = entry.getValue();
				if (list.size() < K)
					continue;

				for (int i = 0; i <= list.size() - K; i++) {
					int len = list.get(i + K - 1) - list.get(i) + 1;
					minLen = Math.min(minLen, len);
					maxLen = Math.max(maxLen, len);
				}
			}

			if (minLen == Integer.MAX_VALUE || maxLen == Integer.MIN_VALUE) {
				System.out.println(-1);
			} else {
				System.out.println(minLen + " " + maxLen);
			}
		}
	}
}

ashMap 활용하여 문자열에서 각 알파벳이 등장한 모든 인덱스를 List 형태로 저장하였다.
이렇게 저장한 이유는 문제 조건 중 하나인 맨 앞과 맨 뒤가 동일한 문자여야 한다는 점을 효율적으로 처리하기 위해서다.

그 후, ist.get(i) 현재 시작 인덱스를, ist.get(i + K - 1) K번째 등장 위치를 나타낸다.
이 두 값을 사용해 K번 등장하는 부분 문자열의 길이를 계산할 수 있다.

부분 문자열의 길이는 list.get(i + K - 1) - list.get(i) + 1로 구하며, 이를 기반으로
최소 길이와 최대 길이를 계속 업데이트하면서 답을 찾아가면 된다.