나의 풀이

처음에는 word 크기에 해당하는 배열을 substring으로 잘라낸 후, 이것이 word의 각 문자의 개수와 같은지 일일이 확인해주는 브루트포스가 떠올랐다. 하지만 이는 시간 복잡도가 O(g*|S|) 이므로 이 문제에서는 90억번의 연산이 필요해진다.

곧바로 이 문제는 투포인터 내지는 슬라이딩 윈도우로 풀어야하는 문제라고 생각했다. 이 문제는 다른 사람의 도움없이 혼자서 히든테스트까지 스스로 생각하며 풀어봤는데, 확실히 슬라이딩 윈도우 문제는 검증을 더 꼼꼼하게 해야겠다는 생각이 들었다.

나는 입력되는 문자를 key 값으로 저장하는 map을 사용했는데 다른 사람들의 풀이를 보니 map을 사용하지 않고 소문자와 대문자를 포함한 new int[104] 크기의 배열을 선언해서 풀 수도 있는 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

class Main {

    static Map<Character, Integer> map = new HashMap<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int wl = Integer.parseInt(st.nextToken());
        int sl = Integer.parseInt(st.nextToken());
        char[] chars = br.readLine().toCharArray();
        for (char c : chars) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        String string = br.readLine();

        int left = 0;
        int right = 0;
        int answer = 0;

        while (true) {
            if (left == sl || right == sl) break;
            char rc = string.charAt(right);

            // 아직 length가 부족한데 이동하는 과정에서 다른 문자를 본다면 left를 오른쪽까지 이동, map 복구
            if (!map.containsKey(rc)) {
                while (left < right) {
                    map.computeIfPresent(string.charAt(left), (character, integer) -> integer + 1);
                    left += 1;
                }
                left += 1;
                right += 1;
                continue;
            } else {
                // map에 저장된 문자이면, 더 추가해야되는지 추가하면 안되는지 확인한다
                if (map.get(rc) == 0) {
                    while (string.charAt(left) != rc) {
                        map.computeIfPresent(string.charAt(left), (character, integer) -> integer + 1);
                        left += 1;
                    }
                    map.computeIfPresent(string.charAt(left), (character, integer) -> integer + 1);
                    left += 1;
                }

                map.computeIfPresent(rc, (character, integer) -> integer - 1);
                if (right - left == wl - 1) answer += 1;
                right += 1;
            }
        }

        System.out.println(answer);
    }
}