[백준/C++] 5052번: 전화번호 목록(G4)

문제

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

5052번: 전화번호 목록

 

 

사용한 알고리즘

2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash)+기초지식

 

풀이

1. 각 테스트케이스마다 전화번호들을 벡터v에 담아준다.
2. 벡터 v를 오름차순 정렬한다. (길이가 짧은 번호가 앞쪽에 오도록)
3. 각 전화번호마다 hash값을 구해준다.
   hash[i][j]는 i번째 전화번호의 j번째 글자까지의 hash값의 합이다.
4. 이중for문을 돌며 짧은 전화번호의 마지막글자 ii의 hash값과 긴 전화번호의 ii의 hash값을 비교해준다.
5. 같은 hash값을 가지는 경우가 있다면 일관성이 없는 목록이므로 NO를 출력하고 아니라면 YES를 출력한다.

 

 

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define X 27
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc; cin>>tc;
    while(tc--){
        int n; cin>>n; cin.ignore();
        vector<string> v;
        // 1. 각 테스트케이스마다 전화번호들을 벡터v에 담아준다.
        for(int i=0; i<n; i++){
            string tmp; cin>>tmp; v.push_back(tmp);
        }
        // 2. 벡터 v를 오름차순 정렬한다. (길이가 짧은 번호가 앞쪽에 오도록)
        sort(v.begin(),v.end());
        // 3. 각 전화번호마다 hash값을 구해준다.
        //    hash[i][j]는 i번째 전화번호의 j번째 글자까지의 hash값의 합이다.
        ll hash[n][10];
        for(int i=0; i<n; i++){
            ll POW=1;
            for(int j=0; j<v[i].size(); j++){
                if(j==0) hash[i][j]=v[i][j]*POW;
                else hash[i][j]=hash[i][j-1]+v[i][j]*POW;
                POW*=X;
            }
        }
        // 4. 이중for문을 돌며 짧은 전화번호의 마지막글자 ii의 hash값과 긴 전화번호의 ii의 hash값을 비교해준다.
        int ck=0;
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                int ii=v[i].size()-1;
                // 5. 같은 hash값을 가지는 경우가 있다면 일관성이 없는 목록이므로 NO를 출력한다.
                if(hash[i][ii]==hash[j][ii]){
                    ck=1;
                    cout<< "NO\n";
                    break;
                }
            }
            if(ck) break;
        }
        // 5. 일관성있는 목록이면 YES를 출력한다.
        if(!ck) cout<< "YES\n";
    }
    return 0;
}