[프로그래머스 코딩테스트 고득점 Kit - 해시] 전화번호 목록

문자열 문제

programmers.co.kr/learn/courses/30/lessons/42577

 

www.acmicpc.net/problem/5052

위 문제와 동일한 문제입니다.

---

[문제 풀이]

 

주어진 문자열이 접두어에 해당하는지 판별하는 문제입니다.

해시 파트에 있지만 문자열로 풀었습니다.

 

이 문제를 처음 백준 온라인 저지에서 봤을 때 해시로 푼다는 생각은 전혀 없었습니다.

 

정해라고 생각했던 풀이는 문자열을 정렬하고 인접한 두 문자열을 비교하는 방법이었습니다.

$O(NlogN)$의 시간 복잡도로 해결이 가능합니다.

그리고 트라이 자료구조를 이용하여 $O(NL)$의 시간 복잡도로 해결이 가능합니다.

 

트라이의 연습을 위해 트라이 자료구조를 사용하였습니다.

트라이에 문자열을 넣으면서 문자열의 끝에 해당하는 노드가 이미 존재한다면 false를 반환하였습니다.

 

다른 사람의 풀이를 보니 해시맵에 문자열을 전부 넣고 문자열들의 접두어가 해시맵에 존재하는지 확인하는 풀이가 있었습니다.

해시맵의 탐색은 $O(1)$이므로 해당 풀이 역시 $O(NL)$에 해결이 가능합니다.

 

---

[소스 코드] / C++

 

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

using namespace std;

class Trie {
public:
    Trie* child[10];
    bool islast;

    Trie (bool islast) {
        this->islast = islast;
        for (int i = 0; i < 10; i++) child[i] = nullptr;
    }

    ~Trie () {
        for (int i = 0; i < 10; i++) delete child[i];
    }

    void push(char c, bool b) {
        if (this->child[c - 48] != nullptr) {
            if (b) this->child[c - 48]->islast = true;
        }
        else this->child[c - 48] = new Trie(b);
    }

    Trie* next(char c) {
        return this->child[c - 48];
    }

    bool insert(string data) {
        int dataSize = data.size();
        Trie* cur = this;

        for (int i = 0; i < dataSize - 1; i++) {
            char c = data[i];
            if (cur->next(c) != nullptr && cur->next(c)->islast) return false;

            cur->push(c, false);
            cur = cur->next(c);
        }

        char c = data[dataSize - 1];
        if (cur->next(c) != nullptr) return false;

        cur->push(c, true);

        return true;
    }
};

bool solution(vector<string> phone_book) {
    Trie root(false);
    bool answer = true;

    for (string data : phone_book) {
        if (!root.insert(data)) {
            answer = false;
            break;
        }
    }

    return answer;
}

 

---

[메모]

 

• c++에는 unordered_set / map이라는 자료구조가 존재한다.
• string.substr(len), string.substr(index, len)
• c++의 delete 키워드는 nullptr를 알아서 걸러준다.