[프로그래머스 lv2] 전화번호 목록 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

 

해설

 

phone_book 배열 내 문자열들에 대하여, 특정 문자열이 다른 문자열의 접두사가 될 때 false를 리턴하는 문제이다. 

가장 쉽게 떠올릴 수 있는 방법은, 이중 for문으로 모든 문자열들을 맞춰보면서 특정 문자열이 다른 문자열의 접두사인지 확인하는 것이다. 

그러나 해당 방법의 시간복잡도는 O(N^2)으로 비효율적이다.

 

그렇다면, phone_book 배열을 단일 for문으로 한번만 순회하면서 문제를 해결할 수 있을까?
(당근 있다!) phone_book의 문자열 길이 순으로 먼저 정렬해 놓는다면, 특정 문자열의 접두사는 해당 문자열 위치의 앞쪽에 있을 것이다. 예를 들어, ["119237", "119", "11", "119240"]을 길이 순으로 정렬하면, ["11", "119", "119237", "119240"] 이 된다. "119237"의 접두사들은 "119237" 보다 길이가 짧으므로 그 앞에 있는 원소들 중에 접두사가 있는지 확인하면 된다.

 

    for (auto s : phone_book) {
        string tmp = "";
        for (auto c : s) {
            tmp += c;
            if (st.find(tmp) != st.end()) return false;
        }
        st.insert(tmp);
    }

 

정렬된 phone_book의 문자열들을 순회하면서 tmp에 문자열의 문자를 한글자씩 더하고 부분문자열을 추출한다.

(substr()을 사용해도 되지만 그냥 한글자씩 붙이는게 더 간단해 보인다.) 

이 때, 이전 문자열들 중 tmp가 있으면 접두사가 있는 것이므로 false를 리턴한다.

이전 문자열들은 unordered_set(해시)에 저장해두면 O(1)에 탐색할 수 있다.

 

 

참고할 사실

set, map, unordered_set, unordered_map의 차이

set과 map은 이진탐색트리로 구현되어있어, 특정 원소를 삽입/삭제할 때 O(logn)의 시간복잡도를 가진다.

unorderd_set과 unordered_map은 해시로 구현되어있어, 특정 원소를 삽입/삭제할 때 O(1)의 시간복잡도를 가진다.

(단, 해시는 충돌이 빈번히 일어날 경우 시간복잡도가 O(n)에 가까워진다.)

 

set과 map의 차이는 value의 존재 여부이다.

해당 문제는 unordered_set(해시)를 이용했으므로 최종 시간복잡도는 O(NlogN)(정렬) + O(N)*O(L)(문자열길이)*O(1) = NlogN이 된다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

bool cmp(string a, string b) {
    if (a.size() < b.size()) return true;
    return false;
}

bool solution(vector<string> phone_book) {

    unordered_set<string> st;
    sort(phone_book.begin(), phone_book.end(), cmp);

    for (auto s : phone_book) {
        string tmp = "";
        for (auto c : s) {
            tmp += c;
            if (st.find(tmp) != st.end()) return false;
        }
        st.insert(tmp);
    }
    return true;
}