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

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

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

 

1. 서론

 

엥...? 스러운 문제. 문제가 어려운 건 아니고 효율성이 중요한데 약간 이상하다,,,

 

2. 문제 풀이

 

전화번호 목록이 주어진다. 접두사가 어쩌고 쓰여있지만 쉽게 말하자면 A번호가 B번호의 앞자리와 일치하면 false를 아니면 true를 반환하는 문제이다. 

 

그래서 난 어떤 번호가 어떻게 겹칠지는 모르기 때문에 for문을 두 번 써서 같은 단어인 경우는 제외하고 크로스 체크를 하면서 조건에 맞으면 바로 false를 반환하도록 했다. 당연히 맞는 코드였지만 효율성 3,4번에서 딱 걸리고 말았다. 그래도 어떤 코드가 나올지 모르니 이중 for문은 어쩔 수 없는 거라 생각해서 정렬 후에 배열을 반으로 나눠서 앞, 뒤만 비교 하자라고 생각했는데 이것도 역시나 효율성은 물론이고 맞았던 테케도 틀리게 나왔다. 

 

이때쯤 난 for문을 의심할 수 밖에 없었는데 '질문하기'를 뒤져보니 for문을 하나만 써야 한다는 것이다. for문을 하나만 쓰는 건 배열을 정렬하고 앞뒤를 비교하는 경우 밖에 없을 텐데 그럼 0번째의 문자열이 접두사가 7번째 값의 접두사면 어떻게 하려고?라는 생각에 이중 for문도 썼던 건데.... 반신반의하면서 그렇게 코드를 고쳤는데 맞았다. 뭐 이런 문제가? 황당 그 자체. 그런 케이스는,, 없었나 봐,,

 

3. 코드 설명

 

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

 

위에서 말한 그대로다. 정렬 후... 배열의 앞뒤를 비교하면서 문자열의 값이 같은지 아닌지 확인한다. 이때 접두사 부분을 구현하기 위해 substr를 사용해줬다. substr는 문자열을 잘라주는 함수이다. 접두사인 만큼 범위는 0부터 비교하는 문자의 크기만큼!!