글 읽기 - [파이썬] 시간초과

gyjinro 3년 전 0

파이썬으로 이진 탐색 트리를 만들어서 풀어 보려고 했는데요.

시간 초과가 나서 계속 틀리네요 ㅠ 어딘가 효율적으로 바꿀 수 있는 부분이나 잘 못 만든 부분이 있을까요?

아니면 파이썬 이진 트리로는 요 문제를 풀 수 없는 걸까요? ㅠ

import sys
root = None


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


def push(x):
    global root
    if not root:
        root = Node(x)
    else:
        parent = root
        node = root
        while node:
            parent = node
            if node.value > x:
                node = node.left
            else:
                node = node.right
        if parent.value > x:
            parent.left = Node(x)
        else:
            parent.right = Node(x)


def del_node(parent, node, sig):
    global root
    if node.right:
        succ = node.right
        if succ.left is None:
            succ.left = node.left
            if parent == node:
              root = succ
            elif sig == 1:
                parent.right = succ
            elif sig == -1:
                parent.left = succ
        else:
            while succ.left:
                p_succ = succ
                succ = succ.left
            p_succ.left = succ.right
            succ.left = node.left
            succ.right = node.right
            if parent == node:
                root = succ
            elif sig == 1:
                parent.right = succ
            elif sig == -1:
                parent.left = succ
    elif node.left:
        if parent == node:
            root = node.left
        elif sig == 1:
            parent.right = node.left
        elif sig == -1:
            parent.left = node.left
    else:
        if parent == node:
            root = None
        elif sig == 1:
            parent.right = None
        else:
            parent.left = None
    del node


def del_max():
    global root
    if root:
        parent = root
        node = root
        while node.right:
            parent = node
            node = node.right
        return parent, node, 1


def del_min():
    global root
    if root:
        parent = root
        node = root
        while node.left:
            parent = node
            node = node.left
        return parent, node, -1


def main():
    global root
    t = int(sys.stdin.readline())
    for _ in range(t):
        k = int(sys.stdin.readline())
        for _ in range(k):
            op, x = sys.stdin.readline().split()
            x = int(x)
            if op == 'I':
                push(x)
            elif root:
                if x == 1:
                    del_node(*del_max())
                else:
                    del_node(*del_min())
        if root == None:
            print('EMPTY')
        else:
            max_num = del_max()[1].value
            min_num = del_min()[1].value
            print(max_num, min_num)


if __name__ == "__main__":
    main()

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

문제

문제

출처

ICPC

[파이썬] 시간초과

gyjinro 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말