[c++] 백준 1202: 전화번호 목록

5052번: 전화번호 목록

문제

코드

/**
 * baekjoon - 5052
 * data structure, string, sorting, tree, trie
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define fio ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

vector<string> teleNum;

int main(){
    fio;
    int t; cin >> t; //testcase

    for (int i = 0; i < t; i++){
        //input
        int n; cin >> n; //n개 전화번호
        string tel;
        for (int j = 0; j < n; j++){
            cin >> tel;
            teleNum.push_back(tel);
        }

        // sorting
        sort(teleNum.begin(), teleNum.end());

        // sol
        bool chk = false;
        for (int a = 0; a < teleNum.size()-1; a++){
            string tmp = teleNum[a];

            if (tmp.length() >= teleNum[a+1].length()) continue;

            string slice = teleNum[a+1].substr(0, tmp.length());
            if (strcmp(tmp.c_str(), slice.c_str()) == 0){
                cout << "NO\n";
                chk = true;
                break;
            }
        }
        if (chk == false) {
            cout << "YES\n";
        }
        
        teleNum.clear();
    }

    return 0;
}

해설

해당 문제는 입력값을 정렬하여 문자열을 비교하여 풀 수 있는 문제이다.

1. 전화번호를 vector<string>teleNum으로 받아들여 입력값을 저장해 준다.
2. teleNum을 오름차순으로 정렬한다. —> sort함수 이용
3. 인접한 두 원소를 가지고 비교하는데, 이 때 먼저 저장된 원소의 길이가 길면 다음차례로 넘겨준다. (continue)
4. 두 번째 원소를 첫 번째 원소의 길이만큼 잘라준다. substr함수를 이용해준다.
5. 인접한 두 원소를 strcmp함수를 이용해 비교하여 준다. strcmp함수는 두 원소가 같으면 0, 왼쪽 원소가 크면 음수, 오른쪽 원소가 크면 양수를 반환해준다.
6. strcmp 함수의 값을 이용해 0이면 접두어가 겹치는 것이므로 “NO”를 출력해주고, 계속 비교하여 “NO”가 출력되지 않으면 for문 마지막에 “YES”를 출력해준다.
7. 다음 테스트케이스를 위해 teleNum을 비워준다. teleNum.clear()