글 읽기 - 파이썬으로 푸는 법을 잘 모르겠습니다.

methe12345 2년 전 0

이진 탐색 트리를 구현하고 삽입할 때마다 높이를 구해서 더하는 식으로 구하였는데..

삽입은O(n) 시간인데 최악의 경우 에서..

시간초과가 나오는 이유는 파이썬이 느려서인가요 아니면 데이터가 커서인가요 아니면 알고리즘 자체가 lower_bound로 다시 해야하나요

lower_bound 도 이렇게 해서 풀겠다! 라는느낌은 알겠는데 막상 구현하려니까 어렵네요..

import sys
input = sys.stdin.readline


class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

class BinarySearchTree(object):
    def __init__(self):
        self.root = None

    def insert(self, data):
        self.current_node = self.root
        count = 0
        if self.current_node != None:
            count += 1
            while True:
                if data < self.current_node.data:
                    if self.current_node.left != None:
                        count += 1
                        self.current_node = self.current_node.left
                    else:
                        count += 1
                        self.current_node.left = Node(data)
                        break
                else:
                    if self.current_node.right != None:
                        count += 1
                        self.current_node = self.current_node.right
                    else:
                        count += 1
                        self.current_node.right = Node(data)
                        break
        else:
            count += 1
            self.root = Node(data)
        return count

n = int(input())
tree = BinarySearchTree()

final = 0

for _ in range(n):
    ret = tree.insert(int(input()))
    final += ret
print(final)

azaraks 2년 전 1

최악의 경우 O(N^2)이기 때문에 안 됩니다.

methe12345 2년 전 0

그럼 lower bound 로 푸는 방식에서 들어간 index는 lowerbound 로 찾고

그 찾은 위치에 삽입하는 연산도 최악의 경우 n의 시간복잡도가 걸리는데

혹시 삽입하는 연산중 빠른 자료구조나 알고리즘이 있을까요?

마땅히 생각나지 않네요

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

문제

문제

출처

ICPC

파이썬으로 푸는 법을 잘 모르겠습니다.

methe12345 2년 전 0

azaraks 2년 전 1

methe12345 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말