[백준 1593] 문자 해독(Java)

문제 링크 : https://www.acmicpc.net/problem/1593

이 문제는 슬라이딩 윈도우 방식을 이용하여 풀 수 있습니다.

문제에서 요구하는 내용이 해당 글자의 순서는 상관없이 글자가 존재하기만 한다면 단어로 선택되는 것이기 때문에 해당 글자 범위만큼 탐색 범위가 고정됩니다. 따라서 슬라이딩 윈도우 방식으로 처음과 끝 포인터만 증가시켜 탐색을 진행합니다.

이 때 현재 인덱스 별 값 계산을 위해 맵을 사용합니다. 맵에 인덱스, 개수 형식으로 저장하여 현재 인덱스가 몇 번 나왔는지를 카운트한 후 맵을 카운팅하면서 현재 체크된 수와 비교합니다.

다음은 코드입니다.

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

class Main{
    static int res = 0;
    static Map<Integer, Integer> map = new HashMap<>();
    static int[] check = new int[100];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int g = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());

        String std = br.readLine();
        String str = br.readLine();

        for(int i=0;i<std.length();i++){
            int idx = std.charAt(i)-'A';
            if(map.containsKey(idx)) map.replace(idx,map.get(idx)+1);
            else map.put(idx,1);
        }

        for(int i=0;i<g;i++){
            int idx = str.charAt(i)-'A';
            check[idx]++;
        }
        search();

        if(l==g){
            System.out.println(res);
            return;
        }

        int start = 1;
        int end = g;
        while(end < l){
            int idxS = str.charAt(start-1) - 'A';
            int idxE = str.charAt(end) - 'A';

            check[idxS]--;
            check[idxE]++;

            search();
            start++;
            end++;
        }

        System.out.println(res);
    }

    static void search(){
        Iterator<Integer> keys = map.keySet().iterator();
        while(keys.hasNext()){
            int idx = keys.next();
            if(check[idx] != map.get(idx)) return;
        }
        res++;
    }
}