Programmers / 전화번호 목록 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 전화번호 목록(2단계)

문제 사이트: https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

문제 설명

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

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

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

제한 사항

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

입출력 예제phone_bookreturn

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

입출력 예 설명

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

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

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

---

 

나의 풀이 (startswith 함수 사용) / 오답

def solution(phone_book):
    phone_book.sort()
    word = phone_book[0]

    for i in range(1, len(phone_book)):
        if phone_book[i].startswith(word):
            tmp = False
            break
        else:
            tmp = True
    return tmp

가장 앞에 숫자만 접두어인 경우로 생각해서 문제를 잘못 풀었음.. 그래서 오답!

나의 코드를 실행해본 결과

 

모범답안 (해시 이용)

def solution(phone_book):
    hash_map = {}
    for i in phone_book:
        hash_map[i] = 1 # 전화번호를 모두 해시로 저장

    # 접두어가 hash map에 존재하는지 찾는다.
    for phone_number in phone_book:
        head = "" # 접두어
        for num in phone_number: #번호 문자열 요소 확인
            head += num 
            if head in hash_map and head != phone_number: 만약 head가 해시에 있으면서 head가 번호와 일치하는 요소가 아니면
                return False # 해당 번호는 head가 접두어가 사용되었음
    return True

딕셔너리를 이용해 phone_book에 있는 각 요소들을 모두 key값으로 등록한다.

그리고 phone_book에 있는 각 요소인 번호 문자열을 하나하나 검사한다.

(코드 참조)

---