[백준] 1593번 - 문자 해독 [Java][C++]

문제 링크

---

1. 문제 풀이

문자열 $S$ 안에 문자열 $W$ 의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 세는 문제로 $g$ 의 범위가 최대 $3,000$, $S$ 의 길이가 최대 $3,000,000$ 이라서 효율적인 탐색이 필요하다. 슬라이딩 윈도우를 기본으로 현재 윈도우에 대한 카운팅 배열을 적용하면 해결할 수 있다.

---

2. 코드

1. 슬라이딩 윈도우 [Java]

카운팅 배열의 경우 알파벳 $A$ 부터 $Z$, 알파벳 $a$ 부터 $z$ 를 모두 포함하는 범위로 설정해줬는데 $A$ 를 int 형으로 형변환하면 $65$, $z$ 를 int 형으로 형변환하면 $122$ 가 되므로 $122 - 65 = 57$ 라서 길이 $58$ 의 배열로 처리해 주었다.

현재 윈도우에 대한 카운팅 배열의 각각의 값들과 초기 $W$ 에 대한 카운팅 배열의 각각의 값이 모두 일치하면 해당 윈도우의 문자들의 순열 중 하나가 $W$ 가 될 수 있다.

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 w = Integer.parseInt(st.nextToken());  // 단어 W의 길이
        int s = Integer.parseInt(st.nextToken());  // 문자열 S의 길이

        char[] W = br.readLine().toCharArray();
        int[] checkW = new int[58];  // 단어 W에 등장한 알파벳을 세는 카운팅 배열
        for (char c : W) {
            checkW[c - 'A']++;
        }

        char[] S = br.readLine().toCharArray();
        int[] checkS = new int[58];  // 단어 S의 윈도우 내에 등장한 알파벳을 세는 카운팅 배열
        for (int i = 0; i < w; i++) {
            checkS[S[i] - 'A']++;
        }

        int cnt = 0;

        // 초기 윈도우에서 W를 만족하면 카운팅
        if (Arrays.equals(checkW, checkS)) {
            cnt++;
        }

        // 윈도우를 이동하며 W를 만족하면 카운팅
        for (int i = 0; i < s - w; i++) {
            checkS[S[i] - 'A']--;
            checkS[S[i + w] - 'A']++;

            if (Arrays.equals(checkW, checkS)) {
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}

2. 슬라이딩 윈도우 [C++]

카운팅 배열의 경우 알파벳 $A$ 부터 $Z$, 알파벳 $a$ 부터 $z$ 를 모두 포함하는 범위로 설정해줬는데 $A$ 를 int 형으로 형변환하면 $65$, $z$ 를 int 형으로 형변환하면 $122$ 가 되므로 $122 - 65 = 57$ 라서 길이 $58$ 의 벡터로 처리해 주었다.

현재 윈도우에 대한 카운팅 배열의 각각의 값들과 초기 $W$ 에 대한 카운팅 배열의 각각의 값이 모두 일치하면 해당 윈도우의 문자들의 순열 중 하나가 $W$ 가 될 수 있다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int wlen, slen;  // 단어 W의 길이, 문자열 S의 길이
    string w, s;
    cin >> wlen >> slen >> w >> s;

    vector<int> cnt_w(58);  // 단어 W에 등장한 알파벳을 세는 카운팅 배열
    for (char c : w) {
        cnt_w[c - 'A']++;
    }

    vector<int> cnt_s(58);  // 단어 S의 윈도우 내에 등장한 알파벳을 세는 카운팅 배열
    for (int i = 0; i < wlen; i++) {
        cnt_s[s[i] - 'A']++;
    }

    int cnt = 0;

    // 초기 윈도우에서 W를 만족하면 카운팅
    if (equal(cnt_w.begin(), cnt_w.end(), cnt_s.begin())) {
        cnt++;
    }

    // 윈도우를 이동하며 W를 만족하면 카운팅
    for (int i = 0; i < slen - wlen; i++) {
        cnt_s[s[i] - 'A']--;
        cnt_s[s[i + wlen] - 'A']++;

        if (equal(cnt_w.begin(), cnt_w.end(), cnt_s.begin())) {
            cnt++;
        }
    }

    cout << cnt;
}

---

3. 풀이 정보

1. 슬라이딩 윈도우 [Java]

언어	시간	메모리	코드 길이
Java 11	300 ms	32600 KB	1361 B

2. 슬라이딩 윈도우 [C++]

언어	시간	메모리	코드 길이
C++ 17	28 ms	7544 KB	1009 B

---