[파이썬] 프로그래머 알고리즘 고득점 Kit - 해시 / 전화번호 목록 완벽해설

문제

 

해설

 

이 문제 역시 해시 자료구조를 사용하는 문제로, 세부적으로 말하면 "세트(Set)" 자료 구조를 활용하는 것이다.

 

풀이 방식을 간단하게 설명하자면, 전화번호부의 모든 전화번호를 set 형식으로 전환을 하고,

전화번호부 안에 있는 각각의 전화번호를 하나하나 불러들인 후, 그 전화번호의 첫번째 숫자부터 하나하나 덧붙여 보면서 그렇게 1. 덧붙여진 숫자가 set 안에 있는지, 그리고 2. 그 숫자가 해당 전화번호랑 같지 않은지를 확인한 후 이 두 조건을 모두 만족할 시 다른 번호가 이 번호의 접두어라는 의미가 되므로 False를 리턴하도록 해주면 된다. (코드 1)

 

다른 하나의 방법은 List를 활용한 방법인데, 이 방법은 전화번호부를 sort 해준 후, 바로 앞에 있는 전화 번호가 바로 뒤에 있는 전화 번호부의 접두어인지만 확인해주면 된다. (코드 2)

 

 

코드

 

코드 1

def solution(phone_book):
    answer = True
	
    # 전화번호부를 set으로 저장
	set_pb = set(phone_book)
    
    # 번호 하나하나 꺼낸다.
    for phone in phone_book:
        num = ""
        # 번호 안에서 숫자를 하나하나 꺼낸다.
        for digit in phone:
        	# 하나하나 붙여본다.
            num += digit
            # 만약 붙여본 숫자가 set_pb 안에 위치하고,
            # 그 붙여본 숫자가 원래 번호랑 같지 않을 때
            # False를 리턴한다.
            if (num in set_pb) and (phone != num):
                return False
    return answer

 

 

코드 2

def solution(phone_book):
    answer = True
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i+1].startswith(phone_book[i]):
            return False
    return answer

 

결과