[c++] BOJ 5052 :: 전화번호 목록

난이도 : 골드 4

걸린 시간 : 20분

 

문제

전화번호 목록 문제 바로가기

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

 

풀이

• b+tree 사용

 

코드

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

using namespace std;

struct Node {
    int num;
    bool isHere;
    Node* next[10] = { nullptr };
    Node(int n, bool b) {
        num = n;
        isHere = b;
    }
};

Node* head[10]; // 시작 번호 노드

bool pushTree(string str) {


    Node* previous = head[str[0] - '0'];
    for (int i = 1; i < str.size(); i++) {
        if (previous->isHere) {
            // 일관성 o
            return false;
        }

        int number = str[i] - '0';
        Node* tmp;
        if (previous->next[number] == nullptr) {
            // 없다면 만들기
            tmp = new Node(number, false);
            previous->next[number] = tmp;
        }
        else {
            // 있다면 기존 것 등록
            tmp = previous->next[number];
            if (i == str.size() - 1) {
                // 기존에 있던 노드인데, 마지막이면 종료 => sort 안하는 대신
                return false;
            }
        }
        previous = tmp;
    }
    previous->isHere = true;
    return true;
}

bool compare(string a, string b) {
    return a.size() < b.size();
}

int main() {
    // 11시 20분 시작
    // b+tree
    // 많아도 9개
    // 숫자, 속한 번호가 있는지, 다음 숫자 노드 집합 => 부모 노드에 숫자가 있으면 안됨

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<string> phoneNumList;
        for (int i = 0; i < n; i++) {
            string tmp; cin >> tmp;
            phoneNumList.push_back(tmp);
        }

        // sort(phoneNumList.begin(), phoneNumList.end(), compare); //

        for (int i = 0; i < 10; i++) {
            head[i] = new Node(i, false);
        }

        bool flag = false;
        for (int i = 0; i < n; i++) {
            if (!pushTree(phoneNumList[i])) { // 일관성 없음
                cout << "NO" << '\n';
                flag = true;
                break;
            }
        }
        if (!flag) {
            cout << "YES" << '\n';
        }
    }
}

 

개선

• unordered_map으로 바꾸어 보았지만 시간이 더 많이 걸리고 메모리도 2배가 됨
• sort의 compare함수를 길이만으로 바꾸니 공간, 시간 복잡도 모두 조금 개선됨
• sort를 없애고 길이가 긴 것을 먼저해도 체크할 수 있도록 조건문을 하나 추가했더니 시간복잡도 약간 개선됨

 

결과

아이디	메모리	시간	언어
gmldms784	91592	184	C++17 / 수정