문제

Programmers 전화번호 목록

핵심

• 전화번호부 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 가장 간단하게 생각해볼 수 있는 것은 2중 루프로 strstr() 또는 contains()로 전화번호부에 다른 전화번호의 접두사가 있는지 검색하는 것이다. 대략 시간복잡도는 $O(N^2\times L)$이기에 해당 알고리즘은 사용할 수 없다.
• 각 전화번호를 해시 자료구조에 저장하여 자신을 제외한 부분 문자열을 해시 자료구조에서 find한다면 시간복잡도를 확 낮출 수 있다. 부분 문자열을 구하고, 문자열을 substr로 구하는 작업이 $O(length^2)$으로 볼 수 있으나, 문자열의 크기는 20이하로 작다.

개선

코드

시간복잡도

• $O(N \times L)$

C++

#include <string>
#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_set<string> s;
    for (auto e : phone_book)
        s.insert(e);
    for (auto e : phone_book) {
        for (length = e.length() - 1; length >= 0; --length) {
            if (s.find(e.substr(0, length)) != s.end()) {
                return !answer;
            }
        }
    }
    return answer;
}

Java

import java.util.HashSet;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        HashSet<String> hs = new HashSet<>();
        for (var e : phone_book)
            hs.add(e);
        for (var e : phone_book) {
            for (int length = e.length() - 1; length >= 0; --length) {
                if (hs.contains(e.substring(0, length)))
                    return !answer;
            }
        }
        return answer;
    }
}