파이썬 / 프로그래머스 / 전화번호 목록

문제

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

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

 

 

풀이

본 문제는 프로그래머스 해쉬 분류에 있는 문제이다.

처음 문제를 풀 때는 정렬로 접근해서 풀려고 했다.

배열을 전화번호 길이의 순으로 역순으로 정렬해서 풀려했으나,,, 효율성은 통과이나 테스트 케이스 10번 오류 실패..

def solution(phone_book):
    answer = True
    phone_book.sort(key=len,reverse=True)
    
    for index, value in enumerate(phone_book) :
        temp_list = phone_book
        del temp_list[index]
        if value.startswith(tuple(temp_list)) :
            return False
    return answer

 

그래서 다시 푼 방식은 똑같이 정렬이나 들어오는 배열의 데이터 타입을 고려한 방식이다.

들어오는 배열의 데이터 타입은 str이다. 이를 sort하게 되면 앞에 놓여진  비슷한 수부터 정렬된다.

이를 이용해서 인접한 배열을 비교하여 문자열의 앞인 접두어가 같은 지 비교하는 방법이다.

 

#정렬 이용
def solution(phone_book):
    answer = True
    phone_book.sort()
    
    for i in range(len(phone_book)-1):
        if phone_book[i] in phone_book[i+1]:
            return False
    return answer

 

다음 방법은 해쉬이다.

해쉬 분류에 있었지만 왜 해쉬로 풀지 몰라 다른 사람 풀이를 보고 공부해보았다.

들어오는 문자열들을 해쉬 키로 넣고 이 해쉬키에 있어서 for을 한 번 더 사용하여

해당 키를 하나씩 쪼개서 쪼갠 문자열이 키 내에 있으면 False를 리턴하는 식으로 짠 방식이다.

#해쉬 이용
def solution_h(phone_book):
    answer = True
    hash_map = {}
    for phone_num in phone_book:
        hash_map[phone_num] = 1
    for phone_num in phone_book:
        temp = ""
        for num in phone_num:
            temp += num
            if temp in hash_map and temp != phone_num: 
                #hash 키에 있는 지, temp가 즉 비교하려는 현재 단어랑 같은 단어인 것을 필터
                return False
    return answer

 

정렬과 해쉬 말고도 트라이라는 방법으로도 풀 수 있다던데,, 

트라이에 대해서 더 공부해봐야할 거 같다.