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

문제 설명

[문제]

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119

• 박준영 : 97 674 223

• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

[제한 사항]

• phone_book의 길이는 1 이상 1,000,000 이하입니다.

• 각 전화번호의 길이는 1 이상 20 이하입니다.

• 같은 전화번호가 중복해서 들어있지 않습니다.

[입출력 예]

풀이

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

회고

해시로 풀어야 했는데 어쩌다보니 리스트로 접근하게 되었다. 정렬을 해야겠다는 생각을 못해서 그런가 뒤에는 브루트포스 방식으로 나아가야할 것 같다 정도만 추측했다.

정렬하면 아무래도 숫자 순서대로 해서 파악하기가 더 쉽다는 것을 깨달았다. 그리고 앞의 번호 만큼 뒤에도 있는지 찾아야 하니까 len()을 이용하면 된다는 것을 이해했다.

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

다른 사람의 풀이를 확인해 보니 정석대로 해시를 이용해서 문제를 푸셨다.

먼저 번호를 해시 맵에 저장하고 전화 번호를 하나씩 가져와서 temp에 전화번호를 한 글자씩 쪼개서 접두어를 누적한다. temp에 저장된 것이 해시 맵에 있는지, 그리고 현재 번호와 완전히 동일하지 않다면 False를 출력한다.

해시 문제이기 때문에 이렇게 푸는 것이 맞지만 리스트보다 더 어렵게 느껴졌다. 그래도 공부하기 위해서 가져와서 코드 분석을 해봤는데 나중에는 해시로 처리해보는 연습도 해야겠다는 생각이 들었다.