[프로그래머스] 전화번호 목록 문제 풀이(해시 Lv. 2) - C++

0. 동일 유형 문제

• [프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
• [프로그래머스] 전화번호 목록 (해시 Lv. 2)
• [프로그래머스] 위장 (해시 Lv. 2)
• [프로그래머스] 베스트 앨범 (해시 Lv. 3)
• Youtube 영상으로 설명을 보고 싶으시다면 다음 영상을 참고하세요.
  

  

 

1. 문제 설명 (출처 : 프로그래머스, 원 출처)

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

• 구조대 : 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

입출력 예 설명

• 예제 #1 : 앞에서 설명한 예와 같습니다.
• 예제 #2 : 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
• 예제 #3 : 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

2. 문제 접근 방식 (문제 단순화 하기)

• 늘 그렇듯, 문제를 간단하게 만들어보는 것이 1단계이다.
• N개의 전화번호가 들어오면, 이중 한 전화번호가 다른 전화번호의 접두어(?)인지를 확인하는 것이다.
• 즉, 아무 한 전화번호가 다른 전화번호의 시작부터의 일부와 동일하면 false
• 서로 연관이 없으면 true를 return 한다

간단한 예시로 시작한다.

• phone_book[0]이 phone_book[2] ('1이라는 값')으로 시작하기 때문에 false를 return 하는 것이 기댓값이다.
• 컴퓨터에게 이 동일한 업무를 시키는 방법은 크게는 2가지, 작게는 3가지라고 생각하여 정리했다.

 

1. 해결책 1 : Sorting 후 1중 Loop을 통해 앞의 번호가 뒷 번호의 접두어인지 확인하는 방법
2. 해결책 2 : 해시를 통해 접두어가 존재하는지를 확인하는 방법

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3-1. Sort/Loop을 사용한 solution

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool solution(vector<string> phone_book)
{
    // 1. phoneBook 배열을 정렬한다.
    sort(phone_book.begin(), phone_book.end());

    // 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;
}

1) Sorting

• sort(phone_book.begin(), phone_book.end()) : phone_book을 오름차순으로 정렬한다.
• 3-1의 solution으로는 대부분의 경우 문제를 해결하기 어렵다
  • 총 1,000,000개의 전화번호가 존재한다면, 최대 비교 횟수는 499,999,500,000회가 된다.
  • 이를 앞/뒤로 서로 접두어인지 확인해야 하니 2배가 되어 약 10조 회의 비교연산이 필요하다.
  • 이는 어떻게 봐도 어려운 문제가 될 것이기 때문에 다른 방법이 필요하다.
• 시험장에서 이런 고민을 하게 된다면, Sorting을 통해 2중 Loop을 1중으로 줄일 수 있는지 고민이 필요하다.

Sorting하고 난 후의 결과

2) 1중 루프로 단방향 비교하기

• 정렬을 하고 나면 크게 두가지가 달라진다
• [0]의 값이 [2]의 값의 접두어인지 확인할 필요가 없어졌다.
  • 정렬을 했기 때문에, [0]/[1]을 비교할 수 있고, [1]/[2]를 비교할 수 있지만, [0]/[2]는 비교하지 않아도 된다.
  • [0]이 [2]의 접두어였다면, [1]도 [2]의 접두어라는 것이 보장되기 때문이다
  • 때로는 sort/loop 조합이 가장 좋은 성능을 내기도 하는데, 이 경우가 그런 경우 중 하나이다.
• [1]의 값이 [0]의 접두어인지 확인할 필요가 없어졌다.
  • 정렬을 했기 때문에, [0]이 [1]의 접두어일 순 있어도, [1]이 [0]의 접두어일 수는 없다.
  • 그래서 3-1의 solution 처럼 양방향을 다 확인하지 않고 단방향만 확인해도 정답을 찾을 수 있게 된다.
• 때론 정렬만 잘해도 웬만한 기법보다 쉽고 빠르게 답을 찾을 수 있는데, 이 경우가 그런 경우 중 하나라고 생각한다.

 

3-2. Hash를 사용한 solution

• 그래도 Hash 문제이고 개념을 이해하는 것이 중요하니 동일한 문제를 Hash로 풀어보자.
• phoneBook의 모든 번호를 Hashing 해두고 나서 접두어 찾는 방식으로 풀어보면 다음 코드가 나온다.

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

using namespace std;

bool solution(vector<string> phone_book)
{
    // 1. HashMap을 만든다.
    unordered_map<string, int> map;
    for (int i = 0; i < phone_book.size(); i++)
        map[phone_book[i]] = 1;

    // 2. 모든 전화번호의 substring이 HashMap에 존재하는지 확인한다.
    for (int i = 0; i < phone_book.size(); i++)
    {
        for (int j = 0; j < phone_book[i].size() - 1; j++)
        {
            string phone_number = phone_book[i].substr(0, j + 1);
            if (map[phone_number])
                return false;
        }
    }

    // 3. 여기까지 오면 접두어가 없다는 것이다.
    return true;
}

1) HashMap 만들기

• HashMap이란 Key-Value의 Pair를 관리하는 클래스이다.
• Key는 phone_number / Value는 1로 설정한다.
• 기본적으로 Hash map은 위와 같이 만들어주는게 정석이다.
• 여기서 Value == 1의 의미는 숫자가 1개 존재한다는 것이다.
• 'Hashing을 한다'라고도 표현하는데, HashMap에 전화번호를 전부 추가해보자. 
• 위 코드의 동작 방식은 다음 예시로 설명하는 것이 가장 쉽게 이해가 가능할 것이다.
• Hash Map을 보고 나면 별게 아니다. 이 문제에서는 Key 값으로 전화 번호를 관리하는 전화번호부다.

 

2) 각 전화번호의 접두어가 HashMap에 존재하는지 확인하기

• 존재하는 모든 전화번호가 HashMap에 등록되었다.
• 이제는 각 전화번호의 접두어가 HashMap에 존재하는지 확인하는 것이다.
• Length 1~전체 길이 - 1 까지의 substring을 떼어서, HashMap에 존재한다면, 접두어가 존재한다고 확인할 수 있다.
• 간단 예시에서는 "12"의 substring인 "1"을 추출한다.
• if (map[phone_number])
  • String이라는 Key가 현재 hash_map에 존재하는지 확인하는 동작이 이게 전부다

 

3) 다 돌아도 없으면 접두어인 전화번호가 없다는 것

• Hash Map을 다 찾아봐도 접두어가 없다면 return true 하면 마무리 된다. 

 

4. 참 쉽죠?

• Hash를 사용해서 문제를 풀 수 있는 방식은 무궁무진하다. 필자도 다른 방식을 먼저 생각해서 풀었는데, 어찌 됐든 정확한 해답을 얻는 빠른 코드라면 전부 좋다.
• 프로그래머스 플랫폼이 정말 좋은 이유는 타 플랫폼 대비 서로의 코드를 보고 배우기 매우 용이하게 되어있다는 점이다. 다른 사람의 코드를 무단 복사나 도용하는 것은 틀린 행위지만, 잘 짜여진 코드를 보는 것만큼 좋은 공부법도 없어 보인다.
• 잘 짜여진 코드는 직관적이고 읽기도 편해서, 이런 코드는 보다 보면 이 사람이 어떤 생각으로 문제를 접근했는지 까지도 보이게 된다. 꼭 문제를 본인만의 방식으로 해결한 뒤에 더 뛰어난 사람들의 코드를 보면서 배우는 시간을 가지면 좋을 것 같다.

 

5. 동일 유형 문제

• [프로그래머스] 완주하지 못한 선수 (해시 Lv. 1)
• [프로그래머스] 전화번호 목록 (해시 Lv. 2)
• [프로그래머스] 위장 (해시 Lv. 2)
• [프로그래머스] 베스트 앨범 (해시 Lv. 3)  
• Youtube 영상으로 설명을 보고 싶으시다면 다음 영상을 참고하세요.