programmers 전화번호 목록

programmers : https://programmers.co.kr/learn/courses/30/parts/12077

 

programmers 해시 level2 전화번호목록 문제입니다.

 

전체스트링 하나가 다른 스트링의 접두사가 되는 부분이 있는지 확인하는 문제입니다.

 

******

사실 이 문제는 .. 테스트케이스가 좀 부족한 문제이지 않나 싶습니다.

O(N^2) 코드가 O(N+NlogN) 코드보다 빠르게 정말 더빠르게 해결됨을 확인했습니다.

아마 N^2 의 완탐코드에서 정답이 빨리 찾아지는 테스트케이스만 모여있기 때문이 아닐까 추측해봅니다

******

 

예를 들어 

12 13 124 2 52 라는 값이 있으면

12 가 124의 접두사가 되기 때문에 정답이 false 가 됩니다.

 

이 문제는 범위가 100만 이기 때문에 사실 N^2 의 복잡도로는 문제가 해결되지 않을줄 알았습니다.

다음은 O(N^2) 코드입니다.

#include <string>
#include <vector>
 
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    
    for(int i = 0; i<phone_book.size()-1; i++){
        for(int j = 0; j<phone_book.size(); j++){
            if(phone_book[i].size()>phone_book[j].size() || i==j) continue;
            bool temp = true;
            for(int k = 0; k<phone_book[i].size(); k++){
                if(phone_book[i][k] != phone_book[j][k]){
                    temp = false;
                    break;
                }
            }
            if(temp){
                answer = false;
                break;
            }
        }
        if(!answer) break;
    }
    
    return answer;
}

그런데 빠른시간내로 통과되더라구요? ??.. 

하지만 문제를 이런식으로 풀게 되면 분명 TLE를 받게될 경우들이 많아질 것이 분명합니다..

 

접두사를 좀더 빠르게 찾는 방법이 무엇일까요?

답은 정렬입니다.

위의 12 13 124 2 3 을 정렬하면

12 124 13 2 3 이라는 사전순서의 정렬이 됩니다.

 

그리고 O(N)으로 문제를 해결하면 됩니다.

접두사가 있는지 없는지는 현재위치와 다음위치만 비교해주면 되기 때문입니다.

다음은 정렬을 이용한 O(N)+O(NlogN) 코드입니다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
 
    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()))
        {
            answer = false;
            break;
        }
    }
 
    return answer;
}