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

1) 문제

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

코딩테스트 연습 - 전화번호 목록

한 번호가 다른 번호의 접두어인 경우를 확인해야 한다.

접두어인 경우가 있으면 false 없으면 true

 

 

2) 풀이

 

단순히 생각하면 이중반복으로 두 번호를 뽑아서 다시 반복문으로 첫 번째 숫자부터 비교하면 되지 않을까?

문제는 해시를 사용하지 않는 다는 점과 반복문이 3중으로 들어간다는 점이다.

역시나 효율성 테스트는 모두 실패했다.

 

다시 해시를 사용하는 쪽으로 방향을 틀어서 고민을 해봤다.

 

3-1) 코드(실패)

bool solution(vector<string> phone_book) {
    bool answer = true;

    for(auto i=phone_book.begin(); i!=phone_book.end() ; i++) {
        for(auto j=next(i,1); j!=phone_book.end(); j++) { //i 다음 번호부터 비교
            if(i == j) continue;
            if(i->length() < j->length()) { //i 번호의 길이가 j보다 짧을 경우에만
                int idx=0;
                for(idx=0; idx<i->length(); idx++) { // i와 j의 번호를 비교
                    if((*i)[idx] != (*j)[idx]) break;
                }
                if(idx == i->length()) answer = false;
            }
        }
    }

    return answer;
}

 

3-2) 코드(통과)

bool solution(vector<string> phone_book) {
    unordered_map<string, int> hash_map;
    for(int i=0; i<phone_book.size(); i++)
        hash_map[phone_book[i]] = 1; //해시에 번호 저장
    for(int i=0; i<phone_book.size(); i++) {
        for(int j=0; j<phone_book[i].size()-1; j++) {
            //첫 번째 글자부터 j+1 길이의 sub string 추출. 단 전체 string 길이의 -1까지
            string phone_number = phone_book[i].substr(0,j+1);
            if(hash_map[phone_number])
                return false;
        }
    }
    return true;
}

 

4) 정리

substr 사용법

간단히 substr(pos, count)에서 pos는 첫 번째 문자의 위치, count는 부분 문자열의 길이

해시를 이용하는 경우 쉽게 해결할 수 있는 문제였다.

문제를 풀면서 찾아보니 sort/loop로도 통과할 수 있었다.

string을 sort로 정렬하는 경우 사전 정렬이 되기 때문에 현재 대상과 다음 대상의 비교만 하면 된다.

위 블로그에서는 [0]이 [2]의 접두어라면 [1]도 [2]의 접두어라는 것이 보장된다고 했지만 사실 그렇지는 않다.

반박 예시 = {"1", "1234", "13"}

다만 [0]이 [1]의 접두어가 아니라면 [1]이후의 모든 요소에서 접두어가 될 수 없기 때문에 [0]은 [1]만 비교하면 된다.

그래서 이 블로그에서 제시하는 이 solution이 가능하다.

bool solution(vector<string> phone_book) {
    // 1. phoneBook 배열을 정렬한다.
    sort(phone_book.begin(), phone_book.end());
    for(auto i : phone_book) {
        cout << i << endl;
    }
    // 2. 1중 Loop을 돌며 앞 번호가 뒷 번호의 접두어인지 확인한다.
    for (int i = 0; i < phone_book.size() - 1; i++)
        if (phone_book[i + 1].find(phone_book[i]) == 0) return false;
    // 3. 여기까지 오면 접두어가 없다는 것이다.
    return true;
}

 

여기서 사용된 find함수는 string에서 특정 string을 찾으면 그 위치를 반환해준다. 찾는 문자열이 없는 경우 -1을 리턴한다.