글 읽기 - [파이썬] 반례를 찾고 싶습니다

leetkdguq73 2년 전 0

4%에서 틀리는데 기존 heap방식을 사용하면 안되는건가요??

반례 알려주실분 있으신가요

import sys
from collections import deque

absq = deque([0])

class absh:
    def __init__(self):
        self.count = 0
    
    def insert(self, data):
        if  self.count == 0:
            absq.append(data)
            self.count += 1
        else:
            temp = data
            absq.append(temp)
            self.count += 1

            child = self.count
            parent = child // 2

            while child != 1 :
                if abs(temp) < abs(absq[parent]) or (abs(temp) == abs(absq[parent]) and temp < 0 and absq[parent] > 0):
                    absq[child] = absq[parent]
                    child = parent
                    parent = parent // 2
                else :
                    break

            absq[child] = temp
    
    def hpop(self):
        if self.count == 0:
            return 0
        
        data = absq[1]
        temp = absq[self.count]
        absq.pop()
        self.count -= 1

        if self.count == 0:
            return data

        parent = 1
        child = 2

        while child < self.count and self.count > 1:
            if abs(absq[child]) > abs(absq[child+1]) or (abs(absq[child] == abs(absq[child+1]) and absq[child+1] < 0 and absq[child] > 0)):
                child += 1
            if abs(temp) < abs(absq[child]) or (abs(temp) == abs(absq[child]) and temp < 0): return data
            
            absq[parent] = absq[child]
            parent = child
            child *= 2
        
        absq[parent] = temp

        return data

            

if __name__ == '__main__':
    N = int(sys.stdin.readline())

    heap = absh()

    for i in range(N):
        a = int(sys.stdin.readline())

        if a == 0:
            print(heap.hpop())
        else:
            heap.insert(a)

jmj0714 2년 전 1

반례입니다.

-2

출력:

-2

정답

-2

leetkdguq73 2년 전 0

반례 부분은 했지만, 아직 틀렸습니다 라고 뜨네요 ㅠㅠ

제가 잘못 풀고 있는건가요?

import sys
from collections import deque

absq = deque([0])

class absh:
    def __init__(self):
        self.count = 0
    
    def insert(self, data):
        if  self.count == 0:
            absq.append(data)
            self.count += 1
        else:
            temp = data
            absq.append(temp)
            self.count += 1

            child = self.count
            parent = child // 2

            while child != 1 :
                if abs(temp) < abs(absq[parent]) or (abs(temp) == abs(absq[parent]) and temp < 0 and absq[parent] > 0):
                    absq[child] = absq[parent]
                    child = parent
                    parent = parent // 2
                else :
                    break

            absq[child] = temp
    
    def hpop(self):
        if self.count == 0:
            return 0
        
        data = absq[1]
        temp = absq[self.count]
        absq.pop()
        self.count -= 1

        if self.count == 0:
            return data

        parent = 1
        child = 2

        while child <= self.count and self.count > 1:
            if child < self.count :
                if abs(absq[child]) > abs(absq[child+1]) or (abs(absq[child] == abs(absq[child+1]) and absq[child+1] < 0 and absq[child] > 0)):
                    child += 1
            if abs(temp) < abs(absq[child]) or (abs(temp) == abs(absq[child]) and temp < 0): return data
            
            absq[parent] = absq[child]
            parent = child
            child *= 2
        
        absq[parent] = temp

        return data

            

if __name__ == '__main__':
    N = int(sys.stdin.readline())

    heap = absh()

    for i in range(N):
        a = int(sys.stdin.readline())

        if a == 0:
            print(heap.hpop())
        else:
            heap.insert(a)

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

문제

문제

출처

ICPC

[파이썬] 반례를 찾고 싶습니다

leetkdguq73 2년 전 0

jmj0714 2년 전 1

leetkdguq73 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말