전화번호 목록

Trie 자료구조를 연습하기 위해 한 문제 더 풀었다. Trie 자료구조를 구현한 Class에 약간의 변형을 가하면 되는 문제였다.

‘insert’함수에서 자식 노드들을 추적하며 내려갈 때, 해당 노드의 data값이 이미 존재한다면, False를 반환하게 코드를 변경했다.

문자열을 Trie자료구조에 insert해 나가면서, False가 반환된 것을 확인하면, 추가를 중지하고 No를 출력한다. 도중에 False가 반환되지 않고 무사히 for문을 끝낸다면 YES를 출력한다.

Plus

추가로, 내가 사용한 반례는 아래와 같다. 문제에서 주어진 예제는 위의 방식대로만 한다면, 정답이 나오지만 아래의 반례에 대해서는 YES를 출력할 것이다. (976이 겹침으로 NO를 출력해야 하는데 말이다.)

Trie 자료구조를 구현할 때, 문자열이 끝나는 Node에만 data를 입력했다. 따라서, 97625999가 insert된 후, 976이 insert돼도 6을 저장한 Node에 data값이 없음음으로 False를 return하지 않는다.

이를 해결하기 위해선 주어진 번호들 중 짧은 번호들 먼저 insert하도록 해야한다. 그래서 코드에 전화번호의 길이에 따라 오름차순 정렬하는 코드를 추가해주었다.

반례

911
97625999
976

CODE

import sys
read=sys.stdin.readline

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(self,string):
        curr_node = self.head

        for char in string:
            #문자열을 구성하는 문자를 순서대로 탐색하며 올라간다.
            #이때, 해당 노드에 data정보가 이미 저장되어 있으면,
            #겹치는 번호라는 뜻임으로, False를 출력한다.
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
                curr_node = curr_node.children[char]
            else:
                curr_node = curr_node.children[char]
                if curr_node.data:
                    return False
        #위의 for문에서 return되지 않고 이 부분까지 무사히 왔다면,
        #겹치는 번호가 없다는 뜻임으로 True 출력!
        curr_node.data = string
        return True

    def search(self, string):
        curr_node = self.head

        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False

        if curr_node.data != None:
            return True

for _ in range(int(read())):
    n=int(read())
    words=list(read().strip() for _ in range(n))
    #여기서 문자열의 길이를 기준으로 오름차순 정렬을 해줘야한다!
    words.sort(key= lambda x: len(x))
    word_trie = Trie()
    for w in words:
        if not word_trie.insert(w):
            print('NO')
            break
    else:
        print('YES')


문자열 집합

Trie 구조에 대해 익힐 수 있었던 뜻 깊은 하루였다. 이 문제에 대해서는 따로 포스팅을 해놓았다.

CODE

import sys
read = sys.stdin.readline

# 아래의 Node, Trie class 구현 부분은
# [https://alpyrithm.tistory.com/74]
# 알파이님의 블로그를 토대로 작성했습니다.

class Node(object):
    # trie 자료구조를 위한 node
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        # dictionary 자료구조 사용
        self.children = {}

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

    # 문자열 삽입
    def insert(self, string):
        curr_node = self.head
        # 삽입할 string 각각의 문자에 대해 자식 Node를 만들며 내려간다.
        for char in string:
            # 자식 Node들 중 같은 문자가 없으면 Node 새로 생성
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            # 같은 문자가 있으면 해당 노드로 이동
            curr_node = curr_node.children[char]

        curr_node.data = string

    # 문자열이 존재하는지 search
    def search(self, string):
        curr_node = self.head

        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False

        if curr_node.data != None:
            return True

n, m = map(int, read().split())

word_trie = Trie()
word_len = list(False for _ in range(501))
# 주어진 문자열과 길이가 같은 문자열에 대해서만 탐색을 진행해
# 시간복잡도 줄이기 위함

for _ in range(n):
    word = read().strip()
    word_trie.insert(word)
    word_len[len(word)] = True
cnt = 0
for _ in range(m):
    word = read().strip()
    if word_len[len(word)] and word_trie.search(word):
        cnt += 1

print(cnt)


풀어야 할 문제

  • 스타트 택시🔥
  • 미네랄
  • 아기 상어
  • 전깃줄 -2
  • 치즈
  • 소가 길을 건너간 이유