백준 20437 문자열 게임 2

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

슬라이딩 윈도우 문제이다.

k개를 포함하는 최소한의 연속된 문자열을 찾으려면
가장 왼쪽과 오른쪽이 같은 문자여야 한다.

그렇기 때문에
3번은 k개를 포함하는 왼쪽과 오른쪽이 같은 최소를 찾으면 되고,
4번은 k개를 포함하는 왼쪽과 오른쪽이 같은 최대를 찾으면 된다.

1) 파이썬 풀이

def solve(w,k):
    d = {}
    minimum = 10001
    maximum = -1
    for i in range(len(w)):
        if w[i] in d:
            d[w[i]].append(i)
        else:
            d[w[i]] = [i]
    for key,array in d.items():
        s = 0
        e = s + k - 1
        if len(array) < k:
            continue
        while e < len(array):
            length = array[e] - array[s] + 1
            minimum = min(minimum, length)
            maximum = max(maximum, length)
            s += 1; e+= 1;
    return minimum, maximum

t = int(input())
for i in range(t):
    w = input()
    k = int(input())
    minimum,maximum = solve(w,k)
    if minimum == -1 or maximum == -1:
        print(-1)
    else:
        print(minimum, maximum)

2)자바 풀이

import java.io.*;
import java.util.*;

public class Main {

    private static int T,K;
    private static String W;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int min = 10001;
            int max = -1;
            W = br.readLine();
            K = Integer.parseInt(br.readLine());
            HashMap<Character, List<Integer>> hashMap = new HashMap<>();
            for (int j = 0; j < W.length(); j++) {
                if (!hashMap.containsKey(W.charAt(j))) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(j);
                    hashMap.put(W.charAt(j), list);
                }else{
                    hashMap.get(W.charAt(j)).add(j);
                }
            }
            for(Character key: hashMap.keySet()){
                int s = 0; int e = s+K-1;
                List<Integer> list = hashMap.get(key);
                if (list.size() < K) continue;
                while (e < list.size()) {
                    int length = list.get(e) - list.get(s) + 1;
                    min = Math.min(min,length);
                    max = Math.max(max,length);
                    s += 1;
                    e += 1;
                }
            }
            if ((min == 10001) || (max == -1)) {
                System.out.println(-1);
            }else System.out.println(min+ " " + max);
        }
    }

}