프로그래머스 42577 전화번호 목록 (C++)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42577

문제 요약

전화번호부에서 한 전화번호가 다른 전화번호의 접두어인 경우에 false를 반환하고, 그렇지 않을 경우 true를 반환하는 함수를 작성하는 문제입니다.

풀이

전화번호 개수의 최댓값이 100만 이므로 모든 전화번호를 서로 대조하며 접두어 관계를 검사하는 방식은 사용할 수 없습니다. (O(N²) 시간 복잡도 이므로 100만 * 100만 = 1조, 시간초과)

 

전화번호부의 각 전화번호는 문자열 형태이므로, 전화번호부 정렬 후 접두어 관계에 있는 전화번호들은 반드시 인접하게 되므로, 전화번호부를 순회하며 인접한 두 문자열을 비교하는 방식으로 접두어 관계를 검사할 수 있습니다.

이 방식을 사용하면 정렬에 필요한 시간복잡도 O(N log N), 순회에 필요한 시간복잡도 O(N) 이므로 시간초과 없이 해결이 가능합니다.

 

그리고 접두어 관계 검사에 std::substr 을 사용할 수도 있지만, 동작 시 내부적으로 메모리 할당을 사용하지 않는 std::compare 를 쓰는 것이 더 효율적입니다.

코드

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

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 + 1]
        		.compare(0, phone_book[i].size(), phone_book[i]) == 0)
            return false;
    }
        
    return true;
}