★★ 해시 - 전화번호 목록 (프로그래머스)

<문제>

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

프로그래머스

 

<코드>

from collections import Counter
def solution(phone_book):
    
    # hash를 dict로 만드는 방법 1
    hash_phone = {}
    for phone in phone_book:
        hash_phone[phone] = 0
    
    # hash를 dict로 만드는 방법 2
    # hash_phone = Counter(phone_book)
    
    for phone in phone_book:
        check = ""
        for i in phone:
            check += i # 각 원소를 하나씩 추가해서 리스트 내에 동일 값이 있는지 체크
            if check in hash_phone.keys() and check != phone:
                return False
    return True

• 정답 풀이 참고 코드

def solution(phone_book):
    answer = True
    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:
                answer = False
    return answer

 

<풀이>

• hash를 만들기 위해 {} 만들어서 원소 하나하나 넣는 방법이 있고 Counter 클래스로 한번에 넣는 방법이 있음
• LIST의 SORTED를 사용하는 경우 테스트 케이스는 정답이지만 3, 4번 오류 (아래 코드 2가지 참고)
• 시간 초과 오류 발생 원인 : LIST의 SORTED에 시간이 오래 소요됨
  • 해결을 위해 원소 찾기에 시간복잡도가 낮은 HASH를 사용

# 3, 4번 sorted 시간초과
def solution(phone_book):
    answer = True
    li = sorted(phone_book, key = lambda x: len(x))
    for i in range(len(li)-1):
        for j in range(i+1, len(li)):
            if li[i] == li[j][:len(li[i])]:
                answer = False
                break
    return answer

# 3, 4번 sorted 시간초과
def solution(phone_book):
    p = len(phone_book)
    answer = True
    phone_book = sorted(phone_book, key=lambda x: len(x))
    for i in range(p):
        for j in range(i+1, p):
            if phone_book[j].startswith(phone_book[i]) == True:
                return False
                break
    return True