[코딩테스트] 해시 - 전화번호 목록

---

문제

 

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

프로그래머스

 

phone_book 전화번호부에 있는 어떤 A라는 번호가 어떤 B라는 번호의 접두어인 경우 False를 리턴, 없는 경우 True를 리턴하는 문제

 

즉 ["A", "A238712"] 일 경우 False

 

 

 

 

---

전략

 

01. 딕셔너리

  문제 제목 자체가 해시를 언급하고 있어서 딕셔너리를 이용해 어떻게 풀 수 있을 지 생각해봤다. 딕셔너리를 하나 만들고 반복문을 돌면서 전화번호부를 검사하는데, 검사가 끝난 전화번호를 딕셔너리를 저장한다. 그리고 딕셔너리의 get()메소드를 이용해 검사하는 전화번호의 처음 일부가 이미 검사가 끝난 전화번호들 중에 하나와 같다면 그 값을 리턴하고 아니라면 None을 리턴하는 걸 이용해 불린값으로 이용하면 될 것 같다.

 

 

---

풀이

def solution(phone_book):
    phone_book.sort()
    check_book = {}
    max_index = 0
    
    for num in phone_book:
        for i in range(0, max_index + 1 if check_book else 1):
            if check_book.get(num[:i]):
                return False

        check_book[num] = 1
        max_index = len(num)
        

    return True

 

 check_book이라는 딕셔너리를 만들고 phone_book의 요소를 차례로 검사하면서 검사가 끝난 요소는 check_book에 담는다.

 

 검사 과정은 check_book에서 길이가 가장 긴 요소의 길이 - 즉, 이미 검사를 끝낸 요소이며 접두어가 될 가능성이 있는 요소의 길이 - 를 max_index에 저장하고 검사할 요소를 길이1부터 max_index만큼 검사해 같은 부분이 있을 경우 False를 리턴하도록 한다.

 

 순회가 끝났음에도 불구하고 같은 부분이 없을 경우 True를 리턴한다.

 

효율성 테스트

 

---

다른 사람의 풀이

 

1. 정렬 및 비교

 

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

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

 

 정수가 아닌 문자열을 정렬할 경우 각 자리의 문자열이 작은 순으로 정렬이 되므로 이를 이용해 풀었다. 예를 들어 ["512", "42", "65"]일 경우 정렬을 하면 ["42", "512", "65"]가 된다.

 

 이렇게 정렬한 뒤 전화번호부의 n번째 요소와 n+1번째 요소만을 비교하기 위해 zip으로 엮어주었고 더 큰 요소인 n+1번째 요소가 n번째 요소의 문자열을 포함하고 있다면 False, 없다면 True를 리턴하도록 하는 풀이다.

 

 문자열 정렬의 특징과 startwith메소드를 적절히 사용한 좋은 풀이다.

 

효율성 테스트