[프로그래머스 / 전화번호 목록 / python]

련지·2023년 6월 20일

python 코딩테스트 코테 파이썬 프로그래머스 해시

코딩 테스트

목록 보기

3/9

오늘의 1솔 ♬

오늘의 문제는 프로그래머스의 Lv.2 전화번호 목록 !
바로 풀고 싶다면 요기로 → 문제 바로가기

문제 설명

문제 요약

전화번호부가 있다
어떤 번호가 다른 번호의 접두사인 경우가 있는지 알고 싶다
만약 그런 경우가 있다면 false, 없다면 true를 반환하라

접두사 ... 라는 말을 써서 헷갈릴 수도 있겠지만 별 거 아니다
예를 들어 아래와 같은 동물 친구들의 전화번호부가 있다면 ?

	고양이: 1234
	강아지: 12
	다람쥐: 237

강아지의 번호는 고양이의 번호의 접두사가 된다
왕왕 냥냥

그리고 해당 경우가 발생하면 true를 반환해야 할 것 같지만 ? false를 반환해야 한다
문제를 제대로 읽어야 하는 이유.txt

변수 설명

	의미	데이터 형식	길이
phone_book	전화번호부	문자열 배열 각 전화번호는 1~20자 중복되는 전화번호는 없음	1 ~ 1,000,000

풀이

첫 구상

문제를 읽자마자 어떻게 풀어야 할지 떠올리는 것은 어렵지 않았다 !

전화번호부를 정렬한다
이 때 전화 번호 ... 숫자니까 숫자로 정렬을 해야 하나 ? ... 싶을 수도 있지만 문자열 정렬을 수행한다

정렬된 전화번호를 차례대로 조회하며

해당 번호 다음부터의 전화번호들 중 2번의 번호로 시작하는 경우가 있는지 찾는다

그런 경우가 있다면 false를 반환하고 반복문을 탈출한다

startswith() 함수를 사용해 간단히 구현해보니 테스트케이스 무난히 통과 ! 야호 ~ ^o^

.
.
.

그래 ... 예상은 했지만 시간 초과가 나더라는
이제 놀랍지도 않아 ! 다른 방법을 찾아보자 !

1️⃣ zip 함수

기존에 두 전화번호를 비교할 때 for문을 2개 사용했는데, 두 배열의 원소들을 쌍으로 엮어주는 zip 함수가 있다고 해서 사용해봤다
양쪽의 면을 하나로 엮어주는 지퍼처럼 두 그룹의 데이터를 서로 엮어준다고 한다 🤐

def solution(phone_book):
    answer = True

    phone_book.sort()
    
    for num_1, num_2 in zip(phone_book[:-1], phone_book[1:]):
        if num_2.startswith(num_1):
            return False

    return answer

전화번호부에 5개의 번호가 있다고 한다면

마지막 번호를 제외한 [ 번호 1, 번호 2, 번호 3, 번호 4 ],
첫 번째 번호를 제외한 [ 번호 2, 번호 3, 번호 4, 번호 5 ]를 zip 함수로 엮는다

결과적으로 (번호 1, 번호 2), (번호 2, 번호 3), ... , (번호 4, 번호 5)와 같이 각 배열 내 동일한 인덱스의 원소끼리 엮이게 된다

이미 문자열 정렬이 된 상태 && 접두사인 경우를 하나만 발견하면 즉시 종료하면 되기 때문에 붙어 있는 두 전화번호만 비교하면 됐던 것

그렇기 때문에 기존 첫 구상에서 사용했던 반복문보다 훨씬 효율적이었다 !

이렇게 시간 초과를 극복하고 효율성 테스트까지 통과 ! 야호 ~ ^o^ ♬

.
.
.

... 그래서 이게 왜 해시 문제인 건데 ?

풀긴 풀었는데 이 문제 ... 도당체 왜 해시 카테고리에 있는 건지 모르겠어서 다른 사람들 의견을 듣자 하니
Trie를 사용하길 의도하고 만든 문제 같다며 ... 그럼 해시가 맞다고 하는 의견이 대다수

Trie 그게 뭔데 ! 공부해주마 ☆

2️⃣ Trie

Trie는 문자열을 Tree로 만들어 문자열 검색 속도를 빠르게 할 수 있는 자료구조다

문자열은 문자열의 각 문자(노드)들이 순차적으로 연결되어 있는 형태로 구성된다

문자열이 있는지 탐색하는 데에는 통상 O(n)의 시간이 소요되지만, 이 Trie를 사용하면 문자열의 길이를 m이라고 할 때 무려 O(m)의 시간밖에 소요되지 않는다 !
빠르다 빨라

검색창에 사용되는 자동 완성 기능이 Trie 활용 사례 중 하나라고 한다

# Trie를 이루는 노드의 구조
class TrieNode:
    def __init__(self):
        self.children = {} # {현재 번호: 다음 번호} 형식의 딕셔너리
        self.end = False # 해당 노드가 전화번호의 마지막 번호인지 여부

# Trie의 생성자와 연산
class Trie:
	# 생성자
    def __init__(self):
        self.root = TrieNode()

	# 새 전화번호를 추가하는 연산
    def insert(self, new_phone: str) -> None:
        node_now = self.root # Trie의 root부터 탐색 시작
        
        for c in new_phone: # 새 전화번호의 각 번호에 대해
            if c not in node_now.children: # 기존에 없던 번호일 경우 
                node_now.children[c] = TrieNode() # 새 노드를 만들어 갈라져나온다
            node_now = node_now.children[c] # 다음 노드로 이동
        node_now.end = True # 모든 번호에 대해 수행 후 해당 번호가 마지막 번호임을 표시

	# Trie에 저장된 번호 중 new_phone의 접두사가 있는지 찾는 연산
    def startswith(self, new_phone: str) -> bool:
        node_now = self.root # Trie의 root부터 탐색 시작

        for c in new_phone: # 새 전화번호의 각 번호에 대해
            if c not in node_now.children: # 기존 전화번호 중 접두사가 없는 경우
                return False # False 반환
            node_now = node_now.children[c] # 다음 노드로 이동
            if node_now.end: # 기존 전화번호가 끝날 때까지 새 전화번호와 일치할 경우 === 접두사
                return True # True 반환
        return True


def solution(phone_book):
    answer = True
    trie = Trie() # Trie(root) 생성

	# 각 전화번호들에 대해
    for phone_number in phone_book:
        if trie.startswith(phone_number): # Trie에 저장된 전화번호 중 접두사가 있을 경우
            return False # False 반환 후 즉시 종료
        trie.insert(phone_number) # Trie에 새 전화번호 추가

    return answer