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

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

문제가 좀 난해해서 생각을 너무 어렵게 했었던 문제다.

 

먼저 정렬을 해서 정리를 해 주고, 오름차순이기에 같은 숫자가 반복되는것 기준으로는 짧은쪽이 앞으로 오게 되니, 번호 하나와 바로 뒤칸의 숫자를 비교한다. 정렬이 되었기에 사용이 가능한 방법.

 

뒤칸의 숫자는 비교의 대상인 숫자의 길이만큼만 앞에서 부터 잘라서 비교한다.

 

앞에서부터 잘랐기에 숫자가 일치하면 접두에 포함이 되어있는 것 이므로 해결.

 

처음에는 문제를 너무 어렵게 생각해서 반복문만 세번을 겹쳤더니, 테스트케이스 마지막에서 10.ms가 나왔었다.

 

하지만 위의 방법을 사용하면 반복을 굳이 무리하게 돌리지 않고도 단순 값만 비교하면 되니 모든 테스트 케이스가 1 미만으로 나와주었다.

 

 

 

 

문제출처 : programmers.co.kr/learn/courses/30/lessons/42577?language=cpp

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