[백준][C++] 5052 전화번호 목록

 

 

 

알고리즘 종류

    - 정렬

    - 트라이

 

 

 

사고 과정

        1. 입력 값을 문자열로 받아서 vector에 저장

        2.  저장한 string 값을 정렬 ( sort()로 정렬하면, 비교 문자열 끼리 문자열 내의 문자를 비교하면서 정렬해준다 )

        3.  i번째 문자열이 i+1번째에 포함되는지 확인하여 포함되면 'NO', 아니면 'YES'를 출력한다. (i와 i+1번째만 비교해도 되는 이유는, 문자열 정렬을 하고 나면 'abc', 'abca', 'abcab', 'abcabc' 처럼 정렬되기 때문에 i와 i+1번째 문자열만 비교해도 알 수 있다.

 

 

 

구현(C++)

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
int t, n;
vector<string> v;
 
bool cmp(string a, string b) {
    return a < b;
}
 
int main(void) {
 
    cin >> t;
    while (t--) {
        // 초기화
        v.clear();
        bool flag = false;
 
        // 입력
        cin >> n;
        for (int i = 0; i<n; i++) {
            string str;
            cin >> str;
            v.push_back(str);
        }
 
        // 정렬
        sort(v.begin(), v.end(), cmp);
 
        // i번째와 i+1번째 비교
        for (int i = 0; i < n-1; i++) {
            string str = v[i];
            int len = str.length();
 
            string str2 = v[i+1].substr(0, len);
            
            if (str == str2) {
                cout << "NO" << endl;
                flag = true;
                break;
            }
        }
 
        if(flag == false) cout << "YES" << endl;
 
    }
}
 
 

 

 

 

시행착오

    - 나는 i번째를 비교할 때, i+1뿐만 아니라 i+1 ~ n까지 모두 비교했다. for문이 2개나 걸리고 비용 낭비였다. 이후 생각을 고쳐서 i번째와 i+1번째만 비교해도 동작한다는 것을 알았다. 

    - Trie를 이용해서 문제해결이 가능한 문제이다.