[백준]5052 전화번호목록

문제설명

트라이로 접근하는 것.

전화번호 중 동일한 접두어가 존재하면 NO를, 존재하지 않으면 YES를 반환한다.

접근

TRI 이용

1. 완전탐색으로 접근하지 않는 이유

완전탐색으로 접근하면 시간복잡도는 엄청나다.

매 테스터케이스마다 N개의 전화를 N!번 비교하여 min(P1,P2)만큼 비교해야 하므로 O(T*N*N!*P)이다. (T는 테스트케이스 수, N은 전화번호 수 P는 전화번호의 자리 수)

따라서 최악의 경우 연산량은 50*10000*10000!*10이 된다.

2. tri접근시 공간복잡도 고려

0~9까지 10개의 수 표현을 10개 표현해야하므로 10^104byte(int선언 기준)가 된다. 256MB를 넘지만, 미리 10개를 다 선언하지 않고 있을 때마다 선언하면 공간복잡도는 많이 줄어든다. n이 10000으로 주어졌으므로 최대 10000\4byte 겠다.(중복없음)

3. 신경써야할 사항

번호를 tri에 삽입할 때마다 중복인지 아닌지 파악하도록 하였는데 자리수가 작은 수부터 입력하여 이를 구현했다. 안 그런다면 11,1 을 입력했을 때 YES가 나오게 된다.

구현

import sys
input = sys.stdin.readline
class NODE:
    def __init__(self):
        self.value = False  # true면 값이 존재
        self.childs = [False for _ in range(10)]

class TRI:
    def __init__(self):
        self.root = NODE()

    '''
    가독성은 떨어지나... 넣다가 중도에 value가 True값 만나면 그대로 종료.
    따라서 return 값은 True or False
    이떄 조건은 정렬되어 있어야 한다. 안그러면 1111,11 이 케이스에서 True나옴.

    for문에서 true나 false받은거 처리하기
    '''

    # root는 childs만 가진다.
    def insertValue(self, bookNumber):
        curNode = self.root

        # curNode를 탐색할건데 값이 없으면 생성.
        for number in bookNumber:
            number = int(number)
            if not curNode.childs[number]:
                curNode.childs[number] = NODE()

            curNode = curNode.childs[number]
            if curNode.value is True:
                return False

        # for문을 빠져나왔다는 건 중복값이 없었고 마지막 문자 노드에 왔단 의미.
        curNode.value = True
        return True


testCase = int(input().rstrip())

for t in range(testCase):
    n = int(input().rstrip())
    bookNumList = [input().rstrip() for _ in range(n)]
    bookNumList.sort()
    tri = TRI()

    for bookNum in bookNumList:
        isOK = tri.insertValue(bookNum)
        if not isOK:
            break

    if isOK:
        print("YES")
    else:
        print("NO")

반성

실행시간이 2500ms가 나왔다. 빠른 사람은 150ms대 코드를 최적화할 필요가 있다.