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

[level 2] 전화번호 목록 - 42577

문제 링크

성능 요약

메모리: 28.1 MB, 시간: 151.43 ms

구분

코딩테스트 연습 > 해시

채점결과

Empty

문제 설명

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

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

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

제한 사항

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

입출력 예제

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

---

알림

2021년 3월 4일, 테스트 케이스가 변경되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

틀린 풀이

초기 생각은 입력값이 문자열이기 때문에 파이선 2중 for문을 사용하여 in을 사용하여 풀려했습니다.

다만 아래 코드는 4개의 실패와 2개의 시간초과를 불러왔습니다.

hash 문제이기 때문에 당연히 시간초과는 날 것이라 예상하고 가볍게 짠 코드였습니다.(실패가 나올줄은 예상 못함)

실패의 원인은 접두사가 아니라 중간에 전화번호가 끼어있는 경우도 False를 리턴하기 때문이 아닐까 예상하여 다시 코드를 작성하였습니다.

def solution(phone_book):
    answer = True
    N = len(phone_book)
    sorted_phone_book = sorted(phone_book,key = lambda x : len(x))
    for i in range(N):
        for j in range(i+1,N):
            if sorted_phone_book[i] in sorted_phone_book[j]:
                return False
    return answer

그래서 아래와 같이 길이에 제한을 두는 형식으로 변경해보니 실패 코드는 사라지고, 시간초과만 불 수 있었다.

def solution(phone_book):
    answer = True
    N = len(phone_book)
    sorted_phone_book = sorted(phone_book,key = lambda x : len(x))
    for i in range(N):
        for j in range(i+1,N):
            temp_len = len(sorted_phone_book[i])
            if sorted_phone_book[i] in sorted_phone_book[j][0:temp_len]:
                return False
    return answer

맞은 풀이

결론적으로는 정렬이 답이었다. Hash 문제라는 틀에 박혀 계속 dict 자료구조에 대한 생각만 하고 있었는데, 아무생각 없이 정렬을 끄적이다 보니 패턴이 눈에 보여 정렬 코드로 문제를 해결하였다.

def solution(phone_book):
    N = len(phone_book)
    sorted_phone_book = sorted(phone_book)
    for i in range(N-1):
        temp_len = len(sorted_phone_book[i])
        if sorted_phone_book[i] in sorted_phone_book[i+1][0:temp_len]:
            return False
    return True