2-4. 슬라이딩 윈도우 [BOJ 1593번]

1. 관련 문제 🎯

문제 : 백준 1593 문자 해독 🦕
난이도 : 골드 5

2. 문제 소개 🧩

1️⃣ 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다.
2️⃣ W를 이루고 있는 g개의 그림문자와, 연구 대상인 벽화에 기록된 마야 문자열 S가 주어졌을 때, 단어 W가 마야 문자열 S에 들어있을 수 있는 모든 가짓수를 계산한다.

• 즉, 문자열 S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다.

3. 문제 풀이 🖌️

이때, 단어 W의 길이가 고정되어 있으므로 슬라이딩 윈도우의 길이를 W의 길이로 고정한 채로 살펴본다!

• 아래의 사진에서 주황색 배열은 단어 W의 배열이다.
  그리고 파란색 배열은 마야 문자열 S를 담은 배열이다.

3-1. 단어 w에 속한 문자의 종류별 개수를 센다.

☝️ 이때, 문자의 종류별 개수를 세는 이유는 w가 문자열 s에 순서 상관없이 들어가지만 문자의 종류별 개수는 변하지 않는다!! (ex. cAda ➡️ aAdc)
따라서 문자의 종류별 개수가 동일하다면 w와 같은 순열이다~!

for(int i=0; i<g; i++){
	gArray[W[i]-'A'] += 1;
}

3-2. 문자열 S의 처음부터 단어 w의 길이까지는 동일하게 문자의 종류별 개수를 센다.

• 슬라이딩 윈도우에서 처음으로 시작하는 단계에서는 처음부터 윈도우 길이까지 모든 연산을 다해주어야 한다!!
  ☝️ 그러나, 2번째 단계부터는 처음을 빼주고 다음으로 들어오는 값만 총 2번의 연산만 해주면 된다~!
• 더 자세한 사항을 살펴보려면, https://velog.io/@da_na/11.-투-포인터-슬라이딩-윈도우-개념

for(int i=0; i<g; i++){
	sArray[S[i]-'A'] += 1;
}

answer++;
for(int j=0; j<g; j++){	
	//단어 w의 순열인지 확인한다. -> 문자 종류별 개수가 모두 동일한 경우 순열이다.
	if(gArray[W[j]-'A'] != sArray[W[j]-'A']){
		answer--;
        break;
    }
}

3-3. 슬라이딩 윈도우를 사용하여 윈도우의 첫번째 문자를 빼고 다음으로 들어오는 값만 총 2번의 연산을 해준다.

for(int i=g; i<s; i++){
	sArray[S[i]-'A'] += 1;	//슬라이딩 윈도우에 다음으로 들어오는 값은 넣어준다.
	sArray[S[i-g]-'A'] -= 1;	//슬라이딩 윈도우의 첫번째 문자는 뺀다.

	answer++;
	for(int j=0; j<g; j++){
    	//단어 w의 순열인지 확인한다. -> 문자 종류별 개수가 모두 동일한 경우 순열이다.
		if(gArray[W[j]-'A'] != sArray[W[j]-'A']){
        	answer--;
            break;
        }
    }
}

4. 전체 코드 🔑

#include <iostream>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);

    int g = 0, s =0;
    string W;   string S;

    int gArray[60] = {0,};
    int sArray[60] = {0,};
    int answer = 0;

    cin>>g>>s;
    cin>>W>>S;
    
    for(int i=0; i<g; i++){
        gArray[W[i]-'A'] += 1;
    }

    for(int i=0; i<g; i++){
        sArray[S[i]-'A'] += 1;
    }

    answer++;
    for(int j=0; j<g; j++){
        if(gArray[W[j]-'A'] != sArray[W[j]-'A']){
            answer--;
            break;
        }
    }

    for(int i=g; i<s; i++){
        sArray[S[i]-'A'] += 1;
        sArray[S[i-g]-'A'] -= 1;

        answer++;
        for(int j=0; j<g; j++){
            if(gArray[W[j]-'A'] != sArray[W[j]-'A']){
                answer--;
                break;
            }
        }
    }
    cout<<answer<<"\n";
}

4-1. 유의할 점 🔥

☝️아스키 코드표를 보면 A,B,C,...,Z와 a,b,c,...,z 대문자와 소문자 사이에 다른 문자도 있는 것을 확인할 수 있다!!

• 처음에는 대문자 26개 + 소문자 26개 = 52개니까 넉넉하게 53개를 잡아서 배열을 만들었다. 그런데 정답이 아니라고 나와서 알아보니, 다른 문자도 대문자와 소문자 사이에 있어서 넉넉하게 배열의 크기를 60으로 잡아주니 "정답"이라고 나왔다!! 😅
• 아래 코드 = 틀린 코드

int gArray[53] = {0,};
int sArray[53] = {0,};

5. 결과 🏆