프로그래머스/고득점키트/해시/전화번호목록

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

알고리즘 연습 - 전화번호 목록 | 프로그래머스

 

해시 두 번째 문제이다. 

전화번호 목록의 어떤 번호가 하나라도 목록내의 다른 번호의 접두사가 된다면, (즉 어떤 번호의 전체가 다른 번호의 앞 전체가 되는 것이다.)

false를 리턴해주고, 그게 아니면 true를 리턴해주면 된다.

해시를 쓴다기보단..  아래와 같이 알고리즘을 설계하였다.

1. 먼저 phone_book을 오름차순으로 sorting하자. 이렇게 한다면, phone_book의 크기를 순회하면서 인접 원소끼리 접두사가 되는지 확인하면 문제 해결을 할 수 있을 것이다. 

 

[구현코드]

---

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

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++){ // i번쨰와 i+1번째를 비교하면 되므로 최대길이 -1 만큼만 탐색한다.
        int cnt = 0;
        for(int j = 0; j < phone_book[i].length(); j++){
            if(phone_book[i][j] == phone_book[i+1][j]){
                cnt++;
                if(cnt == phone_book[i].length()){
                    answer = false;
                    break;
                }
            }
        }
    }
    return answer;
}