[프로그래머스] 전화번호부 - python 해결 과정

일단 문제는 아래와 같다. 

https://programmers.co.kr/learn/courses/30/lessons/42577?language=python3 

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

 

 

첫 시도 방법

1. phone_book을 숫자 길이순으로 정렬

["12", "123", "456", "5678"]

2. 맨 처음 원소가 나머지 원소의 접두어인지 비교. 비교가 끝나면 다음 원소를 기준으로 비교.

 

Code

def solution(phone_book):
    # 방법 1 
    # 낮은 길이의 숫자부터 정렬
    phone_book.sort(key=len)
    
    for i in range(len(phone_book)):
        for j in range(i+1, len(phone_book)):
            if phone_book[j].startswith(phone_book[i]):
               return False
    answer = True
    return answer

 

이렇게 하면 정확도 테스트는 100% 통과하나 효율성 테스트에서 '시간 초과'로 실패한다. 

 

 

 

 

두번째 시도 방법

대체 어떻게 하면 이 문제를 풀 수 있을까? 고민하다가 결국 다른 사람의 풀이를 봤다.

정렬을 굳이 문자열 길이순으로 할필요는 없고 사전순으로 정렬한후 비교해도 풀리는 문제다.

 

1. 문자열을 사전순으로 정렬

2. 이전 문자열이 다음문자열로 시작되는지 검사

 

def solution(phone_book):
    # 방법 2
    # 사전식으로 분류
    # 12 13 2 24 3 3444 6
    phone_book.sort()
    for k in range(len(phone_book)-1):
        if phone_book[k+1].startswith(phone_book[k]):
            return False
    answer = True
    return answer

 

이 문제는 해시를 통해서 풀수도 있다고 하는데, 굳이 해쉬를 쓸 필요는 없을것 같다.