[프로그래머스] 전화번호 목록 _ Python 해시Lv.2

"전화번호 목록" (출처:프로그래머스)

문제 설명

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

구조대 : 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입니다.

 

 

Solution 1: sort( ) 후 약간의 아이디어 

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

phone_book 을 우선 정렬한 후에

phone_book[i] 가 phone_book[i+1]의 앞부분과 같으면 바로 false를 반환하게끔 코드를 짰다

 

Solution 2: 해시맵 정석

def solution(phone_book): 

    # 1.Hash map생성
    hash_map = {} 
    for nums in phone_book: 
        hash_map[nums] = 1 
    
    # 2.접두어가 Hash map에 존재하는지 찾기 
    for nums in phone_book: 
        arr = "" 
        for num in nums: 
            arr += num
    
            # 3. 본인 자체일 경우는 제외
            if arr in hash_map and arr != nums:       
                return False 
                
    return True

 

Solution 3: sort( )와 startswith( ) 사용하기

def solution(phoneBook):
    phoneBook.sort()

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

sort를 해준후 zip으로 본인(p1)과 본인의 다음값(p2)을 묶음 처리해준다.

for문을 돌면서 startwith 함수를 이용해 p2가 p1으로 시작하는지 검사한다.

 

zip( )

zip 함수는 여러 개의 iterable자료형의 크기가 동일할 때 사용한다. ( 크기가 다를경우 순서대로 생성후 None값 삽입)

iterable 자료형의 각각의 요소를 나눈 후 순서대로 묶어서 요소 개수만큼 새로운 iterable 자료형을 생성

• -for문과 사용을 많이 한다
  ex)    for x, y in zip(range(10), range(10)) :

 

startswith( )

startswith는 문자열이 특정문자로 시작하는지 여부를 알려줌 (true, false 반환)