[프로그래머스 / 해시] 전화번호 목록 - Python

🌱 문제

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

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

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

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

🪴 접근방식

정렬을 이용하자

길이가 긴 문자열은 어차피 접두사가 되지 못한다는 것을 깨닫고 문자열 길이를 기준으로 리스트를 정렬하면 될 것이라 생각했다. 그럼에도 계속 효율성 오류가 났다. 값을 기준으로도 정렬해줘야 더 빠르게 접두사인 문자열을 찾을 수 있다는 것을 몰랐다.

또 한가지는 이중 for문을 사용할 필요가 없다는 것. 자신이 바로 다음 문자열의 접두사인지 아닌지만 확인하면 된다. 왜냐하면 이미 값을 기준으로 정렬을 해주었기 때문에, '119' 다음다음에 '11945'가 나오면 어떡하지를 걱정할 필요가 없다. 그 중간에 '1194'든 '1195'든 어딘가에서 걸려서 False를 반환할 것이다.

🌳 풀이

def solution(phone_book):
    # 문자열길이 순으로 정렬
    phone_book.sort(key=len)
    # 값 기준으로 정렬
    phone_book.sort()
    
    for i in range(len(phone_book)):
        if i == len(phone_book) - 1:
            return True
        elif phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            return False
            
    return True