[프로그래머스] 전화번호 목록 풀이

 


1. 문제

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

2. 풀이

2.1. 딕셔너리(해쉬)를 이용한 풀이

  • prefix_dic이라는 dictionary 에 모든 단어를 집어 넣습니다.
  • for문을 돌면서 문자 길이 -1 까지 체크를 하면서 dictionary에 해당 문자열이 존재하는지 확인합니다.
  • 문자열의 길이가 20이 최대이기 때문에 속도에 문제가 없는 소스코드입니다.
def solution(phone_book):
    answer = True
    prefix_dic = {}
    for x in phone_book:
        prefix_dic[x] = True
        
    for x in phone_book:
        for i in range(0, len(x)-1):
            if x[:i + 1] in prefix_dic.keys():
                answer = False

    return answer

2.2. 정렬 후 zip을 이용한 풀이

  • string을 정렬하면 사전순서대로 자연스럽게 정렬이 됩니다.
  • 아래와 같이 zip을 사용하면 i와 i+1 인덱스의 요소를 가져오면서 계속해서 비교하여 굉장히 빠르게 문제를 해결할 수 있습니다.
def solution(phoneBook):
    phoneBook = sorted(phoneBook)

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