[해시] 전화번호 목록 (프로그래머스, Level 1)

Soorim Yoon·2022년 9월 12일

코테 해시

알고리즘 & 코딩테스트

목록 보기

10/67

문제

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

phone_book 리스트 안에 있는 숫자들 중 한 숫자가 다른 숫자의 접두사(맨 앞부터 연이은 몇 자리가 동일)인 경우 False를 출력한다. 접두사 관계인 숫자가 없는 경우 True를 출력한다.

풀이

해시는 데이터를 빠르게 넣거나 가져올 때 사용하는 기법이다. 실행 시간을 단축하고, 실행을 효율화하기 위해 해시 자료구조를 사용한다.
만약 본 문제에 리스트를 사용한다면 효율성 테스트를 통과할 수 없다.

코드

정답 코드

def solution(phone_book):
    answer = True
    hash = {}
    
    # 해시 테이블 만들기
    for i in phone_book:
        hash[i] = 1
    
    # phone_book 배열의 번호들을 하나씩 조회(i)함
    # 조회한 숫자(i)를 첫 글자부터 한 글자씩 추가해가면서 hash 테이블에 같은 번호가 있는지 조회함
    # 본인 숫자의 접두사가 되는 숫자가 있는지 조회함
    for i in phone_book:
        temp = ''
        for j in i:
            temp += j
            # 해당 숫자의 일부분인 temp와 동일한 숫자가 hash에 있으면, 그 숫자가 접두가사 됨
            # 단, 그 숫자가 자기자신인 경우는 제외 ("119"는 "119"의 접두사가 아님)
            if temp in hash and temp != i:  
                answer = False
                
    return answer

코드 실행 결과

시간 초과 코드

위 아이디어로 코드를 구현할 때 꼭 hash를 사용해야 하는지 궁금했다. 딕셔너리를 생성하지 않고 주어진phone_book 배열을 이용해 해당 배열의 요소들을 하나씩 탐색하면서 접두사 관계인 번호가 있는지 찾아보았다.

그 결과 시간 초과가 나타나며 효율성 점수를 받지 못했다. 코드의 효율화를 위해 가능하다면 무조건 딕셔너리와 해시 자료구조를 사용해야 겠다.

def solution(phone_book):
    answer = True
    
    for p in phone_book:
        tmp = ''
        for i in p:
            if tmp in phone_book and tmp != p:
                answer = False
                break
            tmp += i
        
    return answer