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

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 : 2중 Loop을 통해 서로가 서로의 접두어인지를 전부 확인하는 방법
2. 해결책 2 : Sorting 후 1중 Loop을 통해 앞의 번호가 뒷 번호의 접두어인지 확인하는 방법
3. 해결책 3 : 해시를 통해 접두어가 존재하는지를 확인하는 방법

 

 

 

 

 

 

 

 

 

 

3-1. 해결책 1 - Loop을 사용한 solution

• 명색이 해시 문제라 해시로 풀어야 한다는 걸 알지만, 시험에서는 유형을 정해주지 않는다는 함정이 있다.
• 시험 상황에서 2중 Loop 외에는 해답이 떠오르지 않았다면 시도해보지 않고 다른 해결책을 찾았을 것이다.
• 하지만 블로그는 내용을 공부/정리/공유하기 위함이니 2중 Loop solution을 간단하게 정리해보자.

def solution(phoneBook):    
    # 1. 비교할 A선택
    for i in range(len(phoneBook)):
        # 2. 비교할 B선택
        for j in range(i+1, len(phoneBook)):
            # 3. 서로가 서로의 접두어인지 확인한다.
            if phoneBook[i].startswith(phoneBook[j]):
                return False
            if phoneBook[j].startswith(phoneBook[i]):
                return False
    return True

print(solution(["6", "12", "6789"]))

1) 2중 Loop을 사용한 상호 비교

• 가장 간단한 방법으로 모든 전화번호를 서로와 비교하는 것이다.
• 간단 예시처럼 총 3개가 있는 경우 0 vs 1 / 0 vs 2 / 1 vs 2 의 순서로 index i와 j가 정의된다.
• 정렬을 해놓으면 다음과 같이 나온다.

index i와 i위치의 값, j와 j위치의 값을 서로 비교한다

• 이렇게 수행하다보면 i==0 / j==2일 때 6이 6789의 접두어이기 때문에 false를 return 하게 된다.
• String1.startswith(String2)
  • String1이 String2로 시작되는지 (String2가 String1의 접두어인지)를 찾아주는 기본 함수이고,
    이 문제에서 사용하기 아주 적합한 함수이다.
  • 필자도 C와 C++을 기반으로 프로그래밍에 입문한 터라 Python의 내제 함수라는 개념이 어색하고, 때로는 너무 날로 먹는(?) 기분이 들기도 한다.
  • 하지만 좋은 것을 아는 만큼 내 퇴근 시간이 단축되고, ms 혹은 us 단위의 성능을 따지지 않는 대부분의 업계에서는 Library를 활용하여 가독성을 높이는 게 원활한 실무를 위해 훨씬 중요하게 여겨진다.
• phone_book[i]가 phone_book[j]로 시작하는지, 반대로 phone_book[j]가 phone_book[i]로 시작하는지 양쪽을 다 확인하여 둘 다 없으면 i/j의 index 값을 바꿔가며 전부 비교하면 된다.
• 혹시 i/j가 늘어나는 순서가 헷갈린다면 손코딩을 강력하게 추천한다. 특히 초반에는 CPU가 동작하는 방식을 한 단계씩 완전히 모사해보는 연습이 단순한 구현 버그와 디버깅 시간을 단축시켜 훨씬 빠르고 효율적인 프로그래머가 되게 해주는 것 같다..
• 결국엔 손이 느린게 문제가 아니라 머리가 느린 게 문제라서 그런 것 같다.

 

3-2. 해결책 2 - Sort/Loop을 사용한 solution

def solution(phoneBook):
    # 1. 전화번호 sorting
    phoneBook.sort()

    # 2. sorting 한 전화번호부를 2개씩 확인해서 접두어인지 확인한다
    for i in range(len(phoneBook) - 1):
        if phoneBook[i+1].startswith(phoneBook[i]):
            return False
    return True

    print(phoneBook)    
    print(phoneBook[1:])
    print(list(zip(phoneBook, phoneBook[1:])))
    
    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

print(solution(["6", "12", "6789"]))

1) Sorting

• phone_book.sort() : phone_book list를 오름차순으로 정렬한다.
• 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-3. Hash를 사용한 solution

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

def solution(phone_book):
    # 1. Hash map을 만든다
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    
    # 2. 접두어가 Hash map에 존재하는지 찾는다
    for phone_number in phone_book:
        jubdoo = ""
        for number in phone_number:
            jubdoo += number
            # 3. 접두어를 찾아야 한다 (기존 번호와 같은 경우 제외)
            if jubdoo in hash_map and jubdoo != phone_number:
                return False
    return True

print(solution(["6", "12", "6789"]))

1) HashMap 만들기

• HashMap이란 Key-Value의 Pair를 관리하는 클래스이다.
• Key는 phone_number / Value는 1로 설정한다.
• 기본적으로 Hash map은 위와 같이 만들어주는게 정석이다.
• 여기서 Value == 1의 의미는 숫자가 1개 존재한다는 것이다.

 

2) 모든 전화번호 Hashing 하기 (Hash Map에 추가하기)

• 'Hashing을 한다'라고도 표현하는데, HashMap에 전화번호를 전부 추가해보자. 
• 위 코드의 동작 방식은 다음 예시로 설명하는 것이 가장 쉽게 이해가 가능할 것이다.
• Hash Map을 보고 나면 별게 아니다. 이 문제에서는 Key 값으로 전화 번호를 관리하는 전화번호부다.

 

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

• 존재하는 모든 전화번호가 HashMap에 등록되었다.
• 이제는 각 전화번호의 접두어가 HashMap에 존재하는지 확인하는 것이다.
• Length 1~전체 길이 - 1 까지의 substring을 떼어서, HashMap에 존재한다면, 접두어가 존재한다고 확인할 수 있다.
• 간단 예시에서는 "12"의 substring인 "1"을 추출한다.
• if jubdoo in hash_map
  • String이라는 Key가 현재 hash_map에 존재하는지 확인하는 동작이 이게 전부다
  • Python은 정말 쉽고 직관적이게 잘 만든 언어인 것 같다.

 

4. 참 쉽죠?

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

 

5. 동일 유형 문제

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