전화번호 목록

문제설명

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

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

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

 

제한 사항

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

입출력 예제

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

 

나의 생각

• 첫번째 방법(실패)

해시맵을 배웠기 때문에 응용을 해야겠다고 생각했다. 전화부호부 백터에서 들어오는대로 앞에서부터 차례대로 짤라가면서 해시테이블에 있는지 조사하면 쉽게 풀수 있을거라 생각했다.

12, 123 이 들어오는경우 12가 먼저 들어오고 123이 들어왔을때 1,12,123 이런 순서로 해시테이블을 조사하면 된다고 생각했다.

#include <string>
#include <vector>
#include <unordered_set>
 
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_set<string> stringSet;
    for (int i = 0; i < phone_book.size(); ++i) {
        stringSet.insert(phone_book[i]);
        for (int j = 0; j < phone_book[i].size(); ++j) {
            string temp;
            for (int k = 0; k < j; ++k) {
                temp += phone_book[i][k];
            }
            if (stringSet.find(temp) != stringSet.end()) {
                answer = false;
                break;
            }
        }
        if (answer == false) break;
    }
    return answer;
}

하지만 내가 생각한 방법은 먼저 들어온것에 대한것에 대해서만 체크할 수 있었고 뒤에 접두사가 될수있는 전화번호가 들어오면 찾을 방법이 없었다. 예를들어 123, 12 순으로 들어오는경우 12를 1,12와 같이 조사하기 때문에 접두사로 판정할 수 없었다.

 

• 두번째 방법(실패)

이번에는 앞에서부터 전부 다 잘라서 미리 넣어놓고 뒤에도 체크하면 되겠다고 생각했다.

#include <string>
#include <vector>
#include <unordered_set>
 
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_set<string> stringSet;
    for (int i = 0; i < phone_book.size(); ++i) {
        for (int j = 0; j < phone_book[i].size(); ++j) {
            string temp;
            for (int k = 0; k <= j; ++k) {
                temp += phone_book[i][k];
            }
            if (stringSet.find(temp) != stringSet.end()) {
                answer = false;
                break;
            }
            stringSet.insert(temp);
        }
    }
    return answer;
}

보기좋게 실패했다. 이런 경우는 input이 12,13인 경우 12의 1과 13의 1을 접두사로 판단해버린다. 너무 성급하게 생각했다. 해시로는 풀 방법이 도저히 생각나지 않았다.

 

• 세번째 방법(성공)

다른 사람들의 코드를 참고하여 해시가 아닌 정렬후 비교하는 방법으로 문제를 풀어보았다.

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

처음에 직관적으로 이해가 가지 않았다. 너무 해시라는 틀에 얽메여 있었던것 같다. 정렬을 하게되면 "1"이라는 애가 제일 먼저 올것이다. 그다음에 오는 숫자들은 1로 시작하면서 뒤에 다른 숫자들이 붙거나 혹은 1보다 큰숫자로 시작하는 것들 뿐이다. 따라서 정렬을 하면 자기 바로 다음것과 비교하여도 문제가 없다.

 

보완할점

• 해시문제인데 해시로 풀지 못함
• 실제 프로그래밍 대회나 코딩테스트에서는 알고리즘을 정해주지는 않으므로 다르게 풀 방법을 빨리 생각해내야 함
• string의 substr, for each문, auto연산자 등 최신 C++ 기법 좀더 활용해야함