[PS] 전화번호 목록

문제

프로그래머스

 

어떤 전화번호가 다른 전화번호의 접두사가 되는 경우가 있는지 확인한다

 

풀이

먼저, 접두사가 되는 경우를 어떻게 확인할 수 있을지를 생각해봤다

해시 문제는 정렬로 푸는 경우가 꽤 있어서 제일 먼저 정렬이 떠올랐다

[113, 345, 11385, 678, 3456]

와 같은 배열이 있고, 오름차순 정렬을 했다고 하자

[113, 11385, 345, 3456, 678]

그럼 접두사로 쓰이거나, 접두사를 쓰는 배열은 서로 인접하게 된다

따라서 정렬 이후에, 인접한 배열이 접두사를 가지는지 확인하면 된다

 

접두사를 가지는 경우는

i번째 배열이 i+1번째의 배열에 정확하게 포함되는 것이므로

i+1번째 배열에서 substr()을 활용하여 가져온 문자열이 i번째 배열과 같은지 확인하면 된다

 

substr()이란?

문자열의 특정 부분을 추출하는 함수이다

substr(5, 2);

와 같이 사용하며,

5번째 인덱스에서 길이 2만큼을 가져오는 코드이다

 

CODE

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

    return true;
}

 

회고

phone_book[i+1]까지 접근해야 하므로 phone_book.size()-1 만큼만 for문을 돌린다

for문 범위에서 사소하게 실수하는 경우가 많으므로 꼼꼼하게 체크하도록 하자