글 읽기 - 아무리해도... 시간복잡도가 계속 터집니다 ㅠㅠㅠ

kdogyun94 3년 전 0

아무리봐도 정답은 맞는거 같은데

아무리 수정해도 시간복잡도가 해결이 안됩니다...

도대체 뭐가 문제일까요ㅠㅠ

class node():
    def __init__(self):
        self.child = {}
        self.finish = False

# 가능한 숫자 : 0 ~ 9
for _ in range(int(input())): # 1 ~ 50
    numbers = [input() for _ in range(int(input()))] # 1 ~ 10000
     # 전화 길이는 최대 10
    numbers.sort()
    
    result = True
    root_node = node()
    
    for number in numbers:
        check_node = root_node
        
        if result == False:
            break
        
        for num in number:
            if check_node.finish == True or result == False:
                result = False
                break
            
            if num in check_node.child.keys():
                child = check_node.child[num]
                check_node = child
            else:
                new_node = node()
                check_node.child[num] = new_node
                check_node = new_node
        check_node.finish = True
            
    if result == False:
        print('NO')
    else:
        print('YES')

slah007 3년 전 1

Trie라는 자료구조에 대해 찾아보세요 이 문제 완전탐색으로는 못 풉니다

kdogyun94 3년 전 0

@slah007 Trie 라는 자료구조에 대해서 찾아봤는데

현재 구현한 방식이랑 같다고 보이는데... 다른가요?

그리고 python에서 startswith라는 함수가 있는데 이걸로 비교해도

시간복잡도에서 문제가 생기지 않더라구요...

제가 잘 몰라서 그런데 Trie랑 어디가 다른지 좀 알려주실 수 있으신가요?

전 암만봐도 비슷해서....ㅠㅠ 함수로 안 뺐을 뿐이지 같다고 보이거든요.....

slah007 3년 전 1

앗 죄송합니다 함수가 없길래 착각했어요 다시 읽어보니까 Trie로 잘 구현 하셨네요.

제출 언어에서 Python3 대신 더 빠른 pypy3로 내시면 됩니다. 제가 예전에 맞기는 했지만 코드 복붙해서 테스트한 점 양해 부탁드립니다.

kdogyun94 3년 전 0

@slah007 감사합니다

pypy3으로 하니까 해결이 됐습니다.

그런데 뭐가 문제인걸까요? 왜 python3으로 하면 느린건지...ㅠ

input도 그냥 쓰는거말고 sys로 써야 시간이 더 줄고 하던데

파이썬의 고질적 문제라고 봐야할까요?

다른 푸시는 분들보면 똑같이 trie를 함수로 해서 풀었다 뿐이지 python3에서 잘 돌아가던데....

정말 알수가없네요ㅠㅠ

그래도 덕분에 해결했습니다! 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아무리해도... 시간복잡도가 계속 터집니다 ㅠㅠㅠ

kdogyun94 3년 전 0

slah007 3년 전 1

kdogyun94 3년 전 0

slah007 3년 전 1

kdogyun94 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말