[백준] 1593번. 문자 해독(JAVA)

문제

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

---

풀이(18분)

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int wordLength = Integer.parseInt(tokenizer.nextToken()); // w의 길이
        int textLength = Integer.parseInt(tokenizer.nextToken()); // text의 길이
        
        String targetWord = reader.readLine();
        String text = reader.readLine();
        
        int[] targetFrequency = new int[52]; // a ~ Z까지 52개
        int[] windowFrequency = new int[52]; // a ~ Z까지 52개
        
        for (char c : targetWord.toCharArray()) {
            updateFrequency(c, targetFrequency, 1);
        } // word 배열 업데이트
        
        int windowStart = 0;
        int matchCount = 0;
        int currentWindowSize = 0;
        
        for (int i = 0; i < text.length(); i++) {
            char currentChar = text.charAt(i);
            updateFrequency(currentChar, windowFrequency, 1);
            currentWindowSize++;
            
            if (currentWindowSize == targetWord.length()) {
                if (Arrays.equals(targetFrequency, windowFrequency)) {
                    matchCount++;
                }
                updateFrequency(text.charAt(windowStart), windowFrequency, -1);
                windowStart++;
                currentWindowSize--;
            }
        }
        System.out.println(matchCount);
    }

    static void updateFrequency(char character, int[] frequencyArray, int delta) {
        if ('a' <= character && character <= 'z') {
            frequencyArray[character - 'a'] += delta;
        } else {
            frequencyArray[character - 'A' + 26] += delta;
        }
    }
}

---

문제 풀이 전략

 

대표적인 슬라이딩 윈도우 문제이다. 

물론, 밀면서 알파벳의 출연 빈도를 봐야 하기 때문에 Arrays.equals를 해야 한다.

Arrays.equals는 시간 복잡도가 O(N)이기 때문에 52만큼의 연산이 소요된다.

 

물론 이를 극한으로 줄이는 방법도 있을 수 있겠지만, 문제 조건 상 그럴 필요는 없다고 생각했기에 다음과 같이 코드를 작성했다.