[백준/C++] 10840번: 구간 성분(G1)

문제

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

10840번: 구간 성분

 

 

 

사용한 알고리즘

• 2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash)
  -> Polynomial Rolling hash
  
  
• 이분 탐색
  -> 참고 자료 : https://royhelen.tistory.com/36

 

 

 

풀이

<main 함수>

1. X[26]배열에 27의 거듭제곱 수를 미리 담아둔다. (X[0]=1, X[1]=27, ... , X[25]=27^25)]
   -> 27이 아니라 max len보다 큰 값으로 해야 함!!!
2. 문자열 N과 M을 입력받는다.
3. |N| <= |M|이 되도록 swap 한다.
4. 탐색할 특정 구간의 길이 len을 줄여가며 find(len)을 한다.
5. find(len)이 리턴 1이면 N과 M에 길이 len의 애너그램이 있다는 뜻이므로 len을 출력한다.
6. 모든 len에서 애너그램을 찾지 못했으면 0을 출력한다.

 

<find 함수>

1. M의 길이 len인 부분 문자열들의 해시값을 벡터 v에 담아둔다.
2. N의 길이 len인 부분 문자열들의 해시값을 구하면서,
   그 값이 벡터 v에 있었는지 이분 탐색을 이용해 확인한다. 있으면 1을 반환한다.
   N의 길이 len 부분 문자열들을 전부 확인했는데도 M과 동일한 해시값이 없으면 0을 반환한다.

 

시간 복잡도

N의 부분 문자열 개수 O(N-L)
M의 부분 문자열 개수 O(M-L)

O(N-L)의 부분 문자열 집합 : O(N)에서
O(M-L)의 부분 문자열이 등장하는지 이분 탐색 : O(logN) 으로 확인

따라서 총 시간 복잡도는 O(NlogN)

---

이 문제에 거의 4시간 걸렸다..
코드 짜는데도 오래 걸렸고
코드 맞게 짠 거 같은데 계속 이상한 값이 나오거나 WA..

맞왜틀했던 이유

1. memset(Mcnt, 0, 26* sizeof(ll) 또는 sizeof(Mcnt)); 해야 되는데 memset(Mcnt, 0, 26);라고 함
   참고 자료 :
   https://kamang-it.tistory.com/entry/C-memoryhmemset%ED%95%A8%EC%88%98%EC%99%80-%EB%B0%B0%EC%97%B4%EC%9D%98-%EC%B4%88%EA%B8%B0%ED%99%94
2. X[M[i]-'a'] 해야 되는데 X[i]라고 함
3. 이분 탐색하기 전에 벡터 v 정렬 안 함;;
4. 해시 충돌 일어남!!!! x를 문자열의 길이보다 크게 잡아야 함!

 

 

 

 

소스코드

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

typedef long long ll;
using namespace std;

// Polynomial Rolling hash
// mod 사용 안함

string N,M;
int Nlen, Mlen;
ll X[26]; // 미리 x의 거듭제곱을 계산하여 넣어둔다

int find(int len){
    ll Mhash=0;
    ll Mcnt[26]; fill(Mcnt,Mcnt+26,0);
    vector<ll> v; // M의 길이 len짜리 구간들의 해시값을 담는 벡터

    // 1. M의 길이 len인 부분문자열들의 해시값을 벡터 v에 담아둔다.
    for(int i=0; i<Mlen-len+1; i++){ // M의 L 순회
        if(i==0) { // 처음에만 해줌
            for (int j = i; j < i + len; j++) {
                Mcnt[M[j] - 'a']++;
            }
            for (int j = 0; j < 26; j++) {
                // 해시값 = 'a'의 개수 * X[0]
                // X[0]은 a를 의미함
                Mhash += Mcnt[j] * X[j];
            }
        }

        v.push_back(Mhash);

        // Mhash와 Mcnt를 업뎃하여 다음 부분문자열을 바라본다.
        if(i!=Mlen-len){
            Mhash -= X[M[i]-'a'];
            Mcnt[M[i]-'a']--; Mcnt[M[i+len]-'a']++;
            Mhash += X[M[i+len]-'a'];
        }
    }
    sort(v.begin(), v.end()); // ★ 이분탐색 전에 정렬 필수!

    ll Nhash=0;
    ll Ncnt[26]; fill(Ncnt,Ncnt+26,0);

    // 2. N의 길이 len인 부분문자열들의 해시값을 구한다.
    for(int i=0; i<Nlen-len+1; i++){ // N의 L 순회
        if(i==0) { // 처음에만 해줌
            for (int j = i; j < i + len; j++) {
                Ncnt[N[j] - 'a']++;
            }
            for (int j = 0; j < 26; j++) {
                Nhash += Ncnt[j] * X[j];
            }
        }
        // 2-1. Nhash 값이 벡터 v에 있었는지 이분탐색을 이용해 확인하고 있으면 1을 반환한다.
         if(binary_search(v.begin(),v.end(),Nhash)) {
             return 1; //있으면 리턴1
         }

        // Nhash와 Ncnt를 업뎃하여 다음 부분문자열을 바라본다.
        if(i!=Nlen-len){
            Nhash -= X[N[i]-'a'];
            Ncnt[N[i]-'a']--; Ncnt[N[i+len]-'a']++;
            Nhash += X[N[i+len]-'a'];
        }
    }
    // 2-2. N의 길이 len 부분문자열들을 전부 확인했는데도 M과 동일한 해시값이 없으면 0을 반환한다.
    return 0;
}




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

    // 1. X[26]배열에 x의 거듭제곱 수를 미리 담아둔다.
    ll x=1;
    for(int i=0; i<26; i++){
        X[i]=x;
        x*=1501; // ★ x를 문자열의 길이보다 크게 잡아야함!
    }

    // 2. 문자열 N과 M을 입력받는다.
    cin>>N>>M;

    // 3. |N| <= |M|이 되도록 swap한다.
    if(N.length()>M.length()){
        string tmp =N;
        N=M;
        M=tmp;
    }
    Nlen=N.length(), Mlen=M.length();

    // len : 탐색할 특정 구간의 길이
    // 4. len을 역순탐색하며 find(len)을 한다.
    for(int len=Nlen; len>0; len--){
        if(find(len)){
            // 5. 길이 len의 같은 성분을 가진 구간을 찾았으면 len을 출력하고 마친다.
            cout<<len;
            return 0;
        }
    }
    // 6. 모든 len에서 애너그램을 찾지 못했으면 0을 출력한다.
    cout<<0;
    return 0;
}