[Programmers] 전화번호 목록 - 해시

문제 url: https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

 

난이도: Lv.2

정답률: 60%

권장 시간: 40분

권장 시간 복잡도: O(NlogN)

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

예를 들어, 전화번호가 다음과 같을 경우:

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

구조대의 번호 119는 지영석의 번호 11 9552 4421의 접두사입니다.

---

전화번호부에 적힌 전화번호를 담은 배열 phone_book이 주어질 때,
어떤 번호가 다른 번호의 접두어인 경우가 있으면 false,
그렇지 않으면 true를 반환하도록 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

• 전화번호부: ["119", "97674223", "1195524421"]
• 119는 1195524421의 접두사이므로, 결과는 false입니다.

입출력 예 #2

• 전화번호부: ["123", "456", "789"]
• 한 번호가 다른 번호의 접두사인 경우가 없으므로, 결과는 true입니다.

입출력 예 #3

• 전화번호부: ["12", "123", "1235", "567", "88"]
• 첫 번째 번호 12는 두 번째 번호 123의 접두사이므로, 결과는 false입니다.

 

---

내 풀이

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

    return True

 

 

해시를 이용한 풀이

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