[BOJ][C++] 백준 1593번: 문자 해독

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

 

문제

마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다.

마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다.

마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 알 수 없는 셈이다.

고고학자들은 W라는 특정 단어를 발굴 기록으로부터 찾고 있다. 그 단어를 구성하는 각 글자들은 무엇인지 알고 있지만, 이것이 고대 기록에 어떤 형태로 숨어 있는지는 다 알지 못한다.

W를 이루고 있는 g개의 그림문자와, 연구 대상인 벽화에 기록된 마야 문자열 S가 주어졌을 때, 단어 W가 마야 문자열 S에 들어있을 수 있는 모든 가짓수를 계산하는 프로그램을 작성하시오. 즉, 문자열  S안에서 문자열 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 계산하라는 뜻이다.

입력

첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000,  g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실제 내용이 들어있다. 모든 문자열은 알파벳으로 이루어지며, 대소문자를 구분한다.

출력

첫째 줄에 W의 순열이 S 안에 있을 수 있는 형태의 개수를 출력한다.

 

풀이

시간제한이 까다롭다.

일단 투포인터를 응용한 슬라이딩 윈도우를 활용해야한다.

 

그리고 주어진 구간에 w의 순열이 존재하는지 판단해야하는데

처음에 단순히 두 문자열을 도는 이중 For문을 이용했더니 시간초과가 났다. (1%)

두번째로는 sort를 이용해서 간편하게 비교해봤는데 또 시간초과가 났다. (2%)

세번쨰로는 알파벳 배열을 만들어서 구성 알파벳을 비교해봤는데 또또 시간초과가 났다 (8%)

그와중에 꾸준하게 퍼센티지는 올라가는게 매우 열받는다

 

아무리 봐도 세번째 방법이 맞는 것 같아서

슬라이딩 윈도우를 좀 더 적극적으로 활용할 수 있도록 코드를 개선했고 

이번엔 드디어 맞았다!

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

bool isIncluded(vector<int>&alphabet) {
    for(int i : alphabet) {
        if(i!=0) {
            return false;
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
    int g, n;
    string w, s;
    cin >> g >> n;
    cin >> w >> s;
    
    // w의 알파벳 구성
    vector<int>alphabet(60, 0);
    for(char c : w) {
        alphabet[c-'A']++;
    }

    // 슬라이딩 윈도우
    int left=0, right=g;
    int ans=0;
    for(int i=left; i<right; i++) {
        alphabet[s[i]-'A']--;
    }
    while(right<=n) {
        // 포함이면 카운트+1
        if(isIncluded(alphabet)) {
            ans++;
        }

        // 윈도우 이동
        alphabet[s[left]-'A']++;
        left++;
        alphabet[s[right]-'A']--;
        right++;
    }
    
    cout << ans;
    
    return 0;
}

 

시행착오

 

85%쯤에서 틀렸습니다가 뜬다면..

슬라이딩 윈도우가 끝까지 가는지 확인하자..

문제 특성상 슬라이딩 윈도우에 사용할 투 포인터의 인덱스의 의미를 명확하게 지정하고 풀어야한다

 

아래는 코드 변천 과정 아카이빙..

코드 변천과정

 

1. 이중 For문을 돌린 초기 코드 : O(n^2) 추정

bool isIncluded(int left, int right) {
    included.assign(g, false);
    
    for(int i=left; i<right; i++) {
        for(int j=0; j<g; j++) {
            if(s[i]==w[j]) {
                included[j] = true;
                break;
            }
        }
    }
    
    for(bool i : included) {
        if(!i) {
            return false;
        }
    }
    return true;
}

 

2. sort를 이용한 두번째 코드 : O(nlogn) 추정

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

int main() {
    int g, n;
    string w, s;
    cin >> g >> n;
    cin >> w >> s;
    
    sort(w.begin(), w.end());

    int left=0, right=g;
    int ans = 0;
    string new_s = "", tmp;
    for(int i=left; i<right; i++) {
        new_s += s[i];
    }
    while(right<n) {
        tmp = new_s;
        sort(tmp.begin(), tmp.end());
        if(tmp==w) {
            ans++;
        }
        
        left++;
        new_s.erase(0,1);
        right++;
        new_s += s[right-1];
    }
    
    cout << ans;
    
    return 0;
}

 

3. 알파벳 배열을 이용한 구성요소 비교

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

bool isIncluded(string s, vector<int>alphabet) {
    for(char c : s) {
        if(alphabet[c-'A']==0) {
            return false;
        }
        alphabet[c-'A']--;
    }
    
    for(int i=0; i<alphabet.size(); i++) {
        if(alphabet[i]!=0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
    int g, n;
    string w, s;
    cin >> g >> n;
    cin >> w >> s;
    
    // w의 알파벳 구성
    vector<int>alphabet(60, 0);
    for(char c : w) {
        alphabet[c-'A']++;
    }

    // 슬라이딩 윈도우
    int left=0, right=g;
    int ans = 0;
    string new_s = s.substr(left, right);
    while(right<n) {
        // 포함여부 판단
        if(isIncluded(new_s, alphabet)) {
            ans++;
        }

        // 윈도우 이동
        left++;
        new_s.erase(0,1);
        right++;
        new_s += s[right-1];
    }
    
    cout << ans;
    
    return 0;
}