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

전화번호 문제 바로가기

문제 분석

전화번호들이 주어지고, 해당 전화번호가 다른 번호의 접두어인 경우가 하나라도 존재하면 false를 그렇지 않으면 true를 출력하는 문제

ex.
[123 , 12345] → false
[123, 45123] → true

---

문제 풀이 과정

초기 접근

1. 처음에 시간 고려 안하고 일단 무작정 “for문 2개 돌려보자“고 생각하고 무지성 코드 작성하다가 당연히 효율성에서 시간초과 발생
2. 문제가 해시에 분류되어 있어서 해시를 사용하려 했으나 아무리 생각해도 시간을 줄일 방법이 생각나지 않았다.
3. 질문 둘러보다가 … sort를 사용하면 시간 줄일 수 있다는 힌트 얻었다 !

문제 풀자

문자열이라서 sort를 사용할 생각을 아예 못하고 있었다…

대충 문자열 몇 개 넣어서 돌려보니, 숫자 순서대로(1), 길이 순서대로(2) 정렬되는 것을 알았다.

→ i번째랑 i+1번째만 비교하면 for문을 다 돌 필요가 없다!

1. 주어진 전화번호 목록 정렬

2. i+1번째 전화번호가 i번째 전화번호 포함하는지 확인

   이 때, 접두사인지 확인하기 위해서는 포함하는 index가 0임을 확인해야 함!

3. 포함하면 false를 리턴

4. 끝까지 확인했을 때, 포함하지 않는다면 true를 리턴

---

코드

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

엄청 간단해서 … 당황스럽다 …