[프로그래머스 42577] 전화번호 목록

• 출처: 프로그래머스 42577
• 분류: 해시 · Lv.2

문제

전화번호 배열 phone_book이 주어진다. 한 번호가 다른 번호의 접두어인 경우가 있으면 false, 없으면 true를 반환하라.

핵심

문자열을 사전순 정렬하면 접두어 관계는 인접한 원소 사이에서만 발생한다. 전체 쌍을 비교할 필요 없이 인접 비교만 하면 된다.

풀이

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

using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());

    for (int i = 0; i < phone_book.size() - 1; i++)
        if (phone_book[i] == phone_book[i + 1].substr(0, phone_book[i].size()))
            return false;

    return true;
}

메모

• 왜 정렬이 통하는가: 문자열 사전순 정렬에서 "119"는 "1195524421" 바로 앞에 온다. 접두어라면 반드시 인접한다. 사이에 다른 문자열이 끼어들 수 없다.
• substr(0, n): 앞에서 n글자를 잘라낸다. 짧은 쪽 길이만큼 잘라서 비교하면 접두어 판별이 된다.
• 해시 분류지만 정렬이 더 간결하다. 해시로 풀려면 각 번호의 모든 접두어를 unordered_set에 넣고 다른 번호가 존재하는지 확인해야 해서 코드가 길어진다.

해시 풀이

#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

bool solution(vector<string> phone_book) {
    unordered_set<string> s(phone_book.begin(), phone_book.end());

    for (const auto& num : phone_book)
        for (int len = 1; len < num.size(); len++)
            if (s.count(num.substr(0, len)))
                return false;

    return true;
}

모든 번호를 set에 넣고, 각 번호의 접두어가 set에 존재하는지 확인한다.

복잡도

N = 번호 개수(최대 1,000,000), M = 번호 최대 길이(20).

풀이	시간	공간
정렬	O(N log N · M)	O(1)
해시	O(N · M²)	O(N · M)

정렬 풀이

• sort: 문자열 비교가 O(M)이고 N개를 정렬하므로 O(N log N · M).
• 인접 비교 루프: N-1번 × substr 비교 O(M) = O(N · M). 정렬보다 작으므로 전체는 O(N log N · M).
• 추가 메모리 없음.

해시 풀이

• set 구축: N개 문자열 삽입, 각 해시 계산이 O(M)이므로 O(N · M).
• 접두어 확인: 각 번호마다 최대 M-1개의 접두어를 substr로 만들고(O(M)) set에서 조회(해시 계산 O(M)). 번호당 O(M²), 전체 O(N · M²).
• set이 N개 문자열을 저장하므로 O(N · M).

M=20으로 고정이라 실질적 차이는 크지 않지만, 정렬 풀이가 시간·공간 모두 유리하다.