[프로그래머스 / Level 2] 전화번호 목록

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

코딩테스트 연습 - 전화번호 목록

문제를 보자마자 단순하게 2중 for문을 사용해서 다 확인해야겠다는 생각을 할 수도 있다.

하지만 그럴경우 시간 복잡도가 1,000,000 * 1,000,000이므로 시간초과가 날 것이다.

 

HINT : 이 문제는 sort와 substr을 통하여 간단하게 해결 할 수 있다.

 

문제 접근법

• phone_book을 sort한다.
• 일반적으로 sort시 오름차순으로 정리가 되므로, phone_book[i]와 phone_book[i + 1]을 phone_book[i]의 길이만큼 자른 문자열을 비교하여 같을 경우 phone_book[i]가 phone_book[i + 1]의 접두사가 된다.

아래는 코드입니다.

#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;
}