[프로그래머스 Level 2] [해시] 전화번호 목록 (C++)

이번 문제는 접두어 문제였습니다.

딱 생각난 아이디어가 이번에도 sort..여서 해시와는 거리가 좀 있습니다만 모로가도 서울만 가면 된다는 마인드(?)로 진행해보도록 하겠습니다.

0. 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

0.0. 제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.

0.1. 입출력 예제

phone_book	return
[119, 97674223, 1195524421]	false
[123,456,789]	true
[12,123,1235,567,88]	false

0.2. 입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

1. 풀이 과정

또 다시 sort를 사용했습니다. 이러면 안되는데 하면서도 강력한 유혹입니다 ㅋㅋㅋㅋ

먼저 phone_book을 sort하고, 앞과 뒤를 비교합니다.

만약 뒤의 길이가 더 짧다면 당연히 둘은 관계가 없을 것이고,

앞과 뒤를 비교했을 때 뒤가 앞을 포함하는 경우 false가 됩니다.

그렇기 때문에 for문을 통해 앞 문자열과 뒷 문자열을 비교해줍니다.

하나라도 접두어에 해당이 되는 순간 answer를 false로 만들고 return합니다.

비교를 할 때 앞에꺼랑 비교하기 떄문에 for문을 돌릴 때 조건식에 phone_book의 size가 아닌 size-1을 넣어줘야 잘못된 메모리를 불러오지 않을 수 있습니다! 주의하세요!!

2. 소스 코드

#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());
    int size = phone_book.size();
    for (int i = 0; i < size-1; ++i){ // size가 아니라 size-1임에 주의!!
        for (int j = 0; j < phone_book[i].size(); ++j){
            if(phone_book[i][j] != phone_book[i+1][j])
                break;
            if (j == phone_book[i].size()-1)
                answer = false;
        }
        if (answer == false)
            break;
    }
    return answer;
}