[BOJ 20437] 문자열 게임2(java)

---

문제

문자열 게임2

---

문제 해설

tc의 개수와 문자열이 주어지고 k만큼 슬라이딩 윈도우를 이용하여

어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이

어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이

이 두가지를 구하면 됩니다.

1. 핵심은 어떤 문자를 정확히 K개 포함하는 것을 어떻게 구현하냐 입니다. 저는 모든 알파벳 - ArrayList를 key와 value로 가지는 해시맵을 이용하여 구현했습니다. ArrayList는 int를 담고 있어 해당 알파벳이 어떤 인덱스에 담겨있는지에 대한 정보를 담았습니다.
   ex) map.get('a') = [3,6,10] --> a알파벳은 주어진 String 3,6,10번 인덱스에 존재합니다.

2. 다음으로 할 일은 해시맵에 존재하는 모든 key-value 값을 꺼내 비교해야 합니다.
   이미 저장할 때 0번 인덱스부터 끝까지 돌며 저장했기 때문에 오름차순으로 정렬이 되어 있습니다.
   그렇기 때문에 정확히 K개를 포함하고 있는 String을 구할 수 있습니다. 모든 K개를 포함하는 String을 구하고 최대 값, 최소 값을 갱신해주면 답을 구할 수 있습니다.

---

풀이 코드

package 알고리즘스터디;

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

public class BOJ20437 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int test_case = 0; test_case < T; test_case++) {
			String w = br.readLine();
			int k = Integer.parseInt(br.readLine());
			// 해시맵으로 알파벳 - list를 k-v로 가지는 구조를 만든다.
			HashMap<Character, ArrayList<Integer>> map = new HashMap<>();
			for (int i = 0; i < 26; i++) {
				ArrayList<Integer> arr = new ArrayList<>();
				map.put((char) (i + 97), arr);
			}
			// get을 이용해 해당 알파벳이 가지고 있는 Arraylist에 현재 인덱스 삽입
			for (int i = 0; i < w.length(); i++) {
				map.get(w.charAt(i)).add(i);
			}
			// 각 해시맵을 돌아 가장 짧은 길이를 구한다.
			int min = 100000;
			int max = 0;
			for (int i = 0; i < 26; i++) {
				// 리스트길이가 k보다는 같거나 커야한다.
				char key = (char) (i + 97);
				ArrayList<Integer> list = map.get(key);
				if (list.size() < k)
					continue;
				for (int j = 0; j < list.size() - k + 1; j++) {
					// k가 1이면 그냥 1 반환 아니면 k 범위 만큼 전부 계산
					min = Math.min(min, k == 1 ? 1 : list.get(j + k - 1) - list.get(j) + 1);
					max = Math.max(max, k == 1 ? 1 : list.get(j + k - 1) - list.get(j) + 1);
				}
			}
			// 모든 리스트의 길이가 k보다 작으면 -1 리턴
			if (min == 100000) {
				System.out.println(-1);
				continue;
			}
			System.out.println(min + " " + max);
		}
	}
}

---