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

전화번호 목록

문제

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

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

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

• 입력
  • phone_book : 전화번호부에 적힌 전화번호를 담은 배열
• 출력
  • bool
    • true : 접두어 존재 X
    • false : 접두어 존재 O

 

제한사항

• 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입니다.

 

구현 아이디어

1. 리스트 데이터 두개를 비교하여 접두사가 있는지 확인한다.

 

실패 코드

# 실패 코드
def solution(phone_book):
        
    for i in range(len(phone_book)):
        for j in range(i + 1, len(phone_book)):
            if phone_book[i] == phone_book[j][0:len(phone_book[i])]
							 or phone_book[j] == phone_book[i][0:len(phone_book[j])]:
                return False
    return True

 

개선된 코드

# 개선된 코드
def solution(phone_book):
    phone_book = sorted(phone_book)

    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1):
            return False
    return True

 

다른 분 코드

from collections import defaultdict

def solution(phone_book):
    hash_map = defaultdict()
    
    for pb in phone_book:
         hash_map[pb]=  1
    
    for pb in hash_map.keys():
        text = ""
        for p in pb:
            text += p
            if text in hash_map and text != pb:
                return False
    return True

 

문법 정리

• str.startswith(str, beg=0, end=len(string))
  • STR : 비교 문자열
  • strbeg : 선택적 매개 변수는 문자열 검색의 시작 위치를 설정
  • strend : 선택적 매개 변수는 문자열의 끝 위치 감지를 설정
• zip( * iterables , strict = False )
  • 기본적으로 zip은 가장 짧은 반복 가능 항복이 소진되면 중지된다. 긴 iterable의 나머지 항목을 무시하고 결과를 가장 짧은 iterable의 길이로 잘라낸다.
  • iterable한 두 객체가 길이가 동일할 때만 해당 로직을 진행하고 싶으면 strict = True를 설정하게 되면 ValueError가 발생한다. strict=True인수가 없으면 길이가 다른 이터러블을 생성하는 모든 버그가 침묵하게 되어 프로그램의 다른 부분에서 찾기 힘든 버그로 나타날 수 있습니다.
• 예제 1.

list(zip(range(3), ['fee', 'fi', 'fo', 'fum']))

# 결과
[(0, 'fee'), (1, 'fi'), (2, 'fo')]

• 예제 2.

list(zip(range(3), ['fee', 'fi', 'fo', 'fum'], strict=True))

Traceback (most recent call last):
  ...
ValueError: zip() argument 2 is longer than argument 1