프로그래머스 > 전화번호 목록 (Python 3)

1. 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려고 한다.

 

전화번호가 다음과 같은 경우, 구조대 전화번호는 영석이의 전화번호의 접두사이다.

- 구조대 : 119

- 박준영 : 97674223

- 지영석 : 1195524421

 

전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 반환하라.

 

 

2. 코드

(1) 1차 코드 - 효율성 테스트 3, 4 실패 (시간 초과)

def solution(phone_book):
    phone_book = sorted(phone_book, key=len)

    for phone in phone_book:
        temp = phone_book.copy()
        temp.remove(phone)

        for t in temp:
            n = len(phone)
            
            if phone == t[:n]:
                return False
    return True

 

def solution(phone_book):
    phone_book = sorted(phone_book, key=len)

    for i, phone in enumerate(phone_book):
        
        for j, t in enumerate(phone_book):
            n = len(phone)
            
            if j != i:
                if phone == t[:n]:
                    return False
    return True

 

 

 

(2) zip, startswith 사용한 코드

def solution(phone_book):
    phone_book = sorted(phone_book)

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

 

 

 

(3) Hash Map 사용한 코드

def solution(phone_book):
    hash_map = {}

    for phone_number in phone_book:
        hash_map[phone_number] = 1

    for phone_number in phone_book:
        temp = ""

        for number in phone_number:
            temp += number
            
            if temp in hash_map and temp != phone_number:
                return False
    return True

 

 

 

 

3. 설명

(1) 1차 코드

- 전화 번호 길이를 기준으로 배열을 sorting하고, phone_book에 있는 전화 번호 하나씩 검토하면서 t[:n]과 배열의 전화번호가 일치하는지 비교한다.

- 아무래도 sorting 후에 2중 for문을 해서 그런지, 시간 초과가 계속 떴다.

 

 

(2) zip, startswith 사용한 코드

- 숫자로 되어 있는 문자열을 sorting하면, 왼쪽에서부터 크기 순서대로 배열된다.

예를 들어, ['119', '9767423', '1195524421']은 ['119', '1195524421', '97674223'] 이렇게 정렬된다.

 

- 따라서, zip(phone_book, phone_book[1:])로 그 다음 원소와 비교하면서 다음 원소가 이전 원소로 시작되는지 startswith()로 검토한다.

 

 

(3) Hash Map 사용한 코드

- 우선 Hash Map을 사용한 이유는, 리스트보다 원소의 존재를 파악하는데 더 낮은 복잡도를 가지고 있기 때문이다. (O(1))

 

- 전화번호를 hash_map에 key값으로 다 저장해둔다.

- 짧은 문자열 통째로 긴 문자열의 앞쪽과 비교하는 것이 아니라, 긴 문자열의 앞쪽부터 하나씩 temp에 더해가며 짧은 문자열과 동일한 요소가 있는지 확인하는 방식이다.

(나는 문자열 통째로를 긴 문자열의 앞쪽과 비교할 생각만 했어서.. 관점의 변화를 확 느낄 수 있었던 코드였다.)

 

- 원소의 개수를 파악하기 위해서도 Hash map이 사용되지만, 특정 원소의 존재를 확인하는데 빠른 속도를 가지고 있다는 장점으로 다양한 문제에서도 활용 가능하다고 생각한다!