[백준] 1593: 문자 해독 - JAVA

27 Dec 2023 in Algorithm on 문자열

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

풀이

문자열 W와 S가 주어진다.

S를 W의 길이만큼 잘라 그 안의 문자 순서를 바꿨을 때 W로 만들 수 있는 개수를 세는 문제이다.

map을 두개 선언하여 하나에는 W에 들어있는 문자와 개수를 담았다.

또 다른 하나는 W의 길이만큼 S를 잘라 개수를 담았다.

슬라이딩 윈도우를 이용해 S를 탐색하면서 map의 개수를 조정하여

map 두 개가 같은지 비교하여 같을 경우 답을 하나 증가시켰다.

---

메모리: 149420KB

시간: 900ms

언어: Java 11

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        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 W = br.readLine();
        String S = br.readLine();

        Map<Character, Integer> wMap = new HashMap<>();
        Map<Character, Integer> sMap = new HashMap<>();
        for (int i = 0; i < g; i++) {
            wMap.put(W.charAt(i), wMap.getOrDefault(W.charAt(i), 0) + 1);
            sMap.put(S.charAt(i), sMap.getOrDefault(S.charAt(i), 0) + 1);
        }
        int answer = 0;
        if (checkMaps(wMap, sMap)) {
            answer++;
        }

        int left = 0;
        int right = g;

        while (right < l) {
            sMap.put(S.charAt(left), sMap.get(S.charAt(left)) - 1);
            sMap.put(S.charAt(right), sMap.getOrDefault(S.charAt(right), 0) + 1);

            if (checkMaps(wMap, sMap)) {
                answer++;
            }

            left++;
            right++;
        }

        System.out.println(answer);
    }

    private static boolean checkMaps(Map<Character, Integer> wMap, Map<Character, Integer> sMap) {
        for (Map.Entry<Character, Integer> entry : wMap.entrySet()) {
            char key = entry.getKey();
            int value = entry.getValue();

            if (!sMap.containsKey(key) || sMap.get(key) != value) {
                return false;
            }
        }

        return true;
    }

}