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

문제 링크

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

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

전화번호부의 번호들 중 한 번호가 다른 번호의 접두어인 경우가 있는 지 확인하는 문제.

풀이

처음에는 브루트포스로 2중 포문을 써서 모든 전화번호를 대조해서 확인하려고 했다.

그렇게 했더니 정확도 테스트에서는 다 맞았지만 효율성 테스트에서 실패했다.

아무래도 모든 경우를 비교하려고 하다보니 시간초과가 났다.

정렬을 해서 어떻게 해야겠다고 생각은 했지만 어떻게 해야할지 잘 떠오르지가 않았다.

나는 숫자로 이루어진 문자열을 정렬하게 되면 숫자기준으로 정렬될 거라고 생각했는데, 문자열이다 보니 사전순으로 정렬이 된다.

이때 i번째 번호와 사전순으로 가장 유사한 번호는 i + 1번째에 있는 번호이다. 그렇기 때문에 for문을 1번만 돌면서 i번째 숫자와 i + 1 번째 숫자만 접두사가 같은지 확인해주면 된다.

비교하는 방법은 나는 substr을 이용해서 비교하는 두 문자열중 길이가 짧은 문자열을 기준으로 두 문자열의 길이를 같게 만든 후 비교하는 방법을 썼는데, find 함수를 썼어도 될 것같다.

 

#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++){
        string Criterion = phone_book[i];
        string Compare = phone_book[i + 1];
        int Min_length = min(Criterion.length(), Compare.length());
        if(Criterion.substr(0,Min_length) == Compare.substr(0,Min_length))
            return false;
    }
    return answer;
}

 

정렬 후 비교하는게 이 문제의 핵심