글 읽기 - 파이썬 왜 틀렸는지 모르겠습니다..

rmsqor4 2년 전 0

이진검색트리로 만들어 풀어보았는데 틀리다고 나오네요.

어디가 문제가 되서 틀렸다고 나오는 걸까요?

파이썬 고수님들 부탁드립니다 . ㅠㅠ

import sys

input = sys.stdin.readline

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

class q:
    def __init__(self):
        self.root = None

    def empty(self):
        if not self.root:
            return True
        return False

    def insert(self, data):
        if self.empty():
            self.root = Node(data)
        else:
            parent = self.root
            node = self.root
            new = Node(data)
            while node:
                if node.data > data:
                    parent = node
                    node = node.left
                else:
                    parent = node
                    node = node.right
            if parent.data > data:
                parent.left = new
            else:
                parent.right = new

    def delete(self, state):
        if self.empty():
            return
        else:
            if state == "1":
                parent = self.root
                node = self.root
                while node.right:
                    parent = node
                    node = node.right
                if parent == node:
                    if self.root.left:
                        self.root = self.root.left
                    else:
                        self.root = None
                else:
                    parent.right = None

            elif state == "-1":
                parent = self.root
                node = self.root
                while node.left:
                    parent = node
                    node = node.left
                if parent == node:
                    if self.root.right:
                        self.root = self.root.right
                    else:
                        self.root = None
                else:
                    parent.left = None

    def search_max(self):
        if self.empty():
            return False
        else:
            node = self.root
            while node.right:
                node = node.right
            return node.data

    def search_min(self):
        if self.empty():
            return False
        else:
            node = self.root
            while node.left:
                node = node.left
            return node.data

t = int(input())
for _ in range(t):
    k = int(input().strip())
    dq = q()
    for _ in range(k):
        a, b = map(str, input().strip().split())
        if a == 'I':
            dq.insert(int(b))

        if a == "D":
            if b == '1':
                dq.delete("1")
            elif b == "-1":
                dq.delete("-1")

    if dq.empty():
        print("EMPTY")
    else:
        print(str(dq.search_max()) + " " + str(dq.search_min()))

gyjinro 2년 전 3

(저도 못 푼 초보지만)일단 반례 드립니다. 화이팅 ^^;

1
7
I 5
I 3
I 7
I 6
D 1
D -1
D -1

출력 EMPTY

정답 6 6

rmsqor4 2년 전 0

정말 감사합니다 ㅠㅠ 덕분에 해결했습니다..

혹시 실례가 안된다면 반례를 어떻게 만드시는지 여쭤봐도 될까요??

gyjinro 2년 전 0

해결 하셨군요 대단하십니다. ㅠㅠ 저는 아직 못 풀었답니다. 아하하 언젠가 풀 수 있겠죠?

일반적으로 반례를 만드는 방법이라기 보다는 이 문제를 제가 계속 틀리다 보니...

이 문제 한정으로 실수 할 수 있는 경우들을 검토해서 반례를 만들어 드렸습니다. ㅠ^ㅠ

rmsqor4 2년 전 0

아 그렇군요 .. 감사합니다.

저도 도움을 드리고 싶은데 많이 부족하네요 ㅠㅠ.

꼭 푸실수 있을 거에요~ 화이팅 하세요 ~

poroli0119 1년 전 0

rmsqor4 님 혹시 풀이하신 코드 알 수 있을까요!!

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

문제

문제

출처

ICPC

파이썬 왜 틀렸는지 모르겠습니다..

rmsqor4 2년 전 0

gyjinro 2년 전 3

rmsqor4 2년 전 0

gyjinro 2년 전 0

rmsqor4 2년 전 0

poroli0119 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말