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

문제

바로가기

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

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

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

 

 

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

 

 

입출력 예

 

 

해결 방법

이 문제는 두 가지 방법으로 풀 수 있다.

1️⃣ 정렬 & 파싱(해시 X)

먼저 전화번호부 목록을 정렬한다.

정렬하는 이유는 나의 바로 다음 원소와만 비교해서 탐색 시간을 줄이기 위해!

 

만약 전화번호 목록이 ["119", "97674223", "1195524421"] 이라면

정렬한 결과는 ["119", "1195524421",  "97674223"]이다.

그럼 119를 접두어로 가지는 것을 찾기 위해서 바로 오른쪽 원소인 "1195524421"만 확인하면 된다.

 

만약 전화번호 목록이 ["119", "1199", "11999"]라서 119를 접두어로 가지는 것이 2개 이상인 경우에도 

우리는 그 개수가 몇개인지는 관심없고 오로지 존재하는지 안하는지만 궁금하기 때문에 여전히 바로 내 바로 다음 원소와만 비교하면 된다.

 

2️⃣ 해시(맵)

맵을 선언하고 아래와 같이 전화번호 목록을 맵에 저장한다.

map<string, bool> m;
for(int i = 0; i < phone_book.size(); i++) {
    m[phone_book[i]] = true;
}

 

그 다음 전화번호 목록을 돌면서 각 전화번호를 0, 0~1, 0~2, 0~3 이런식으로 파싱한 후 맵에 해당하는 문자열이 있는지 확인하면 된다.

예를 들어 전화번호부 목록이 ["119", "97674223", "1195524421"] 인 경우

map["119"] = true

map["97674223"] = true

map["1195524421"] = true 

이렇게 저장되어있을 것이다.

 

이때 현재 확인하고 싶은 문자열이 "1195524421"인 경우

"1"

"11"

"119"

"1195"

.

.

이런식으로 앞에서부터 하나씩 길이를 늘려가며 맵의 원소를 탐색하는 것이다.

 

주의해야 할 점은 자기 자신은 접두어로 인식하지 않게 해야 하기 때문에

아래처럼 두번째 for문을 돌때 (현재 전화번호 길이 - 2)까지만 탐색할 수 있도록 해야 한다.

for(int j = 0; j < phone_book[i].size() - 1; j++)

 

해시를 사용한 것보다 정렬을 사용한 방식이 훨씬 빠르다.

 

 

내 코드

1️⃣ 정렬 & 파싱

// 구현, 문자열
#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++) {
        string s1 = phone_book[i];
        string s2 = phone_book[i+1];
        if(s1.size() <= s2.size()) {
            if(s2.substr(0, s1.size()) == s1) {
                return false;
            }
        }
    }
    return true;
}

 

2️⃣ 해시(맵)

// 구현, 해시, 맵
#include <string>
#include <vector>
#include <map>
using namespace std;

bool solution(vector<string> phone_book) {
    map<string, bool> m;
    for(int i = 0; i < phone_book.size(); i++) {
        m[phone_book[i]] = true;
    }
    for(int i = 0; i < phone_book.size(); i++) {
        string num = "";
        for(int j = 0; j < phone_book[i].size() - 1; j++) {
            num += phone_book[i][j];
            if(m[num] == true) return false;
        }
    }
    return true;
}