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

☎ 전화번호 목록 문제 풀어보기

😃 나의 코드

def solution(phone_book):
    phone_book.sort()
    for prefix_idx, prefix_phone in enumerate(phone_book):
        for target_phone in phone_book[prefix_idx+1:]:
            if prefix_phone == target_phone[:len(prefix_phone)]:
                return False
    return True

우선 일반적인 풀이입니다. 먼저 해야할 것은 phone_book에 사전 작업으로 사전형으로 정렬해줍니다. 이렇게 정렬하게 되면 절대로 특정 인덱스 앞은 특정 인덱스의 prefix가 될 일이 없기 때문에 시행을 조금이나마 줄여줍니다. 같은 O(n^2)의 시간 복잡도이기 때문에 크게 영향은 없습니다.

if target_phone.startswith(prefix_phone):
	return False

이제 처음부터 끝까지 확인하면서 해당 인덱스 뒤에 있는 번호와 비교하여 해당 인덱스가 prefix가 되는 지 확인합니다. 저는 slice를 이용하여 substring을 비교했지만, string의 startswith() Method를 쓰면 더 간단하게 구현할 수 있습니다

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}

class Trie(object):
    def __init__(self):
        self.head = Node(None)

    def insert_search(self, string):
        curr_node = self.head
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
            if curr_node.data:
                return False
        curr_node.data = string
        return True

def solution(phone_book):
    phone_book.sort()
    trie = Trie()
    for phone in phone_book:
        if not trie.insert_search(phone):
            return False
    return True

이 문제는 Trie로도 풀 수 있습니다. Trie는 Tree 의 한 종류로 검색을 뜻하는 retrieval에서 온 단어입니다. Prefix tree라고도 하며 특정 문자열을 검색할 때 시간복잡도가 O(m)(m: 문자열의 최대 길이)밖에 안 되는 강력한 문자열 검색 자료 자료구조로 주로 검색에서 자동 완성(Autocomplete)를 구현할 때 사용됩니다.

class Node(object):
    def __init__(self, key, flag=None):
        self.key = key
        self.flag = flag
        self.children = {}
        
class Trie(object):
    def __init__(self):
        self.head = Node(None)
        
    def insert_search(self, string):
        curr_node = self.head
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(True)
            curr_node = curr_node.children[char]
            if curr_node.flag:
                return False
        curr_node.flag = True
        return True

def solution(phone_book):
    phone_book.sort()
    trie = Trie()
    for phone in phone_book:
        if not trie.insert_search(phone):
            return False
    return True

Tree의 구현 방법과 비슷합니다. 이 문제에서는 prefix의 존재만을 알면 끝나도 되기 때문에 insert대신 insert_search라는 Method를 구현합니다. Trie는 문자열 insert시 문자열에 해당하는 마지막 글자 Node에 flag를 추가해서 해당하는 문자열이 존재함을 알려줍니다. 이 flag를 활용하여 문제를 풀어 봅시다.

insert_search는 일반적인 Trie의 insert처럼 작동하다가 만약 그 과정에서 특정 Node의 flag가 True임을 확인하면 즉, prefix의 존재를 확인하면 바로 False를 반환하는 방식으로 문제를 해결했습니다.

Written with StackEdit.