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

전화번호 목록(Level 2)

문제
전체 문제 보기

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

접근법

이 문제를 정렬을 통해서도 풀 수 있지만 Hash 카테고리에 있는 문제이니 만큼 출제 의도에 맞춰서 Hash를 써서 풀어 보았다. C++의 std::unordered_map은 해시 테이블의 자료구조로 삽입과 탐색에 \(O(1)\)의 성능을 보여준다. 이 해시 테이블을 활용하면 최대 전화번호 수를 \(n\), 전화번호 길이를 \(l\) 라고 한다면 \(O(l \cdot n)\) 시간 복잡도로 풀이가 가능하다. 그리고 사실상 전화번호 길이는 최대 20이기 때문에 \(O(n)\) 이라고도 볼 수 있다. 아래와 같은 방법으로 문제를 해결했다.

 

(2021.08.05 추가: 해당 문제에 트라이 자료구조를 활용하면 더 효율적인 해결이 가능하다. 해당 풀이는 이 링크에서 확인 할 수 있다.  - [트라이를 활용한 풀이 보기] ) 

 

먼저 해시맵에 다음과 같이 모든 경우의 수에 대해서 전화번호를 등록한다. 예제는 위의 첫번째 입출력 예제를 사용했다.

▲ 해시 테이블에 저장된 모습

이때 다시 한번 모든 전화번호에 대해서 다음과 같이 반복 한다.

• key가 119인 원소
  • ht에 key가 1인 원소가 있는가? 있다면 false
  • ht에 key가 11인 원소가 있는가? 있다면 false
• key가 97674223인 원소
  • ht에 key가 9인 원소가 있는가 있다면 false
  • ht에 key가 97인 원소가 있는가? 있다면 false
  • ( ... 중략 ...)
  • ht에 key가 97674223인 원소가 있는가? 있다면 false
• (... 이하 생략 ...)

반복문을 무사히 통과한다면 유효한 전화번호부로 인정하고 true를 반환한다. 이때 주의할 점은 자신은 대입하지 않아야 한다. 문제 조건에서도 중복된 번호는 없다고 명시되어있으며, 자기자신과 동일한 번호는 자기자신으로 항상 존재하기 때문에 모든 경우에 대해서 false가 나오게 된다.

• 해시테이블 ht 생성 (key: string(전화번호) , value: int(카운트))
• 전화번호(string)을 key로 가지는 value에 전화번호가 등록되었음을 1로 마킹한다.
• 모든 전화번호에 대해서 다음 반복문을 시행한다.
  • 전화번호 처음 1자리 부터 ~ 최대길이가 될때 까지 해시맵에 동일한 번호가 등록되었는지 확인한다. (여기서 동일한 번호가 등록 되었다는 뜻은 다른 번호의 접두어인 경우를 뜻한다.)
  • 만약 해시맵에 동일한 번호가 등록되었다면 false를 반환한다.
• 반복문을 무사히 빠져나왔다면 어떤 번호가 다른 번호의 접두어인 경우가 없다는 뜻이다.

구현

#include <string>
#include <vector>
#include <unordered_map>
#include <iostream>

using namespace std;

bool solution(vector<string> phone_book) {

    unordered_map<string, int> ht;

    // 해시 테이블에 모든 전화번호를 등록하고 value를 1로 마킹
    for(auto number : phone_book)
        ht[number] = 1;

    for(auto number : phone_book)    // 모든 전화번호에 대해서
        for(int i = 1; i < number.length(); i++) //  모든 경우의 수에 대해서 (자기자신 제외)
            if(ht.find(number.substr(0,i)) != ht.end())    // 중복된 번호가 있다면 false
                return false;

    return true;
}