[Algo] Programmers level 2 전화번호목록(Hash)

Sol 1

def solution(phone_book):
    answer = True
    phone_book.sort()
    dic = {}
    for phone in phone_book:
        dic[phone] = True
        
    for phone in phone_book:
        
        for n in range(1, len(phone)):
            prefix = phone[:n]
            if prefix in dic.keys():
                return False
    
    return answer

• phone 번호로 해시를 만들고, key를 for문으로 돌리는데, 해당 번호의 1번째부터 len(key)-1까지를 슬라이스 하면서 key에 값이 존재하는 지를 판단한다

Sol 2

def solution(phone_book):
answer = True
phone_book.sort(key=lambda x : len(x))


for i in range(len(phone_book[0]),len(phone_book[-1]) ):
    
    temp = []
    for phone in phone_book:
        if len(phone) >= i:
            temp.append(phone[:i])
            
    if len(temp) > len(set(temp)):
        return False
return answer

• 이렇게 풀면 테케 2개에서 실패가 났다
• 전화번호 길이는 1~20이라 했으므로, 전화번호 길이를 기준으로 정렬을 했고, 가장 짧은 길이의 숫자부터 가장 긴 길이의 숫자까지 문자열을 슬라이스했다. temp 배열에 넣은 뒤, set()으로 중복 제거를 했을 때 차이가 난다면 어딘가 접두어로 쓰이고 있는 것이라 판단했다. 대부분의 경우 맞을 수 있는데 만약 "1234"와 "12345"를 123까지만 슬라이스 하면 중복 제거 되어버리기 때문에 틀린 답이 나올 수 있다.