글 읽기 - 어떤 논리상의 문제가 있는지 모르겠습니다.

2000flora 3년 전 0

처음에는 이분탐색을 이용했더니 시간초과가 나서 우선순위 큐를 이용해서

중간값은 정수로, 중간값 이외의 수들은 heapq구조에 left, right배열을 생성해서 차례로 입력/갱신되도록 구현하였습니다.

5%에서 틀렸다고 나오는데 반례나 논리상의 오류를 찾아 주시면 감사하겠습니다.

import sys
input = sys.stdin.readline
import heapq

# 3개의 배열을 만든다. -> left, mid, right의 3개를 만들어서 입력되는 숫자가 만약에 mid보다 크다면 right의 제일 작은 수와 비교해서 넣을지 말지 결정
# mid보다 작다면 left에 넣어줌
N = int(input())


left, mid, right = [], 0, []
answer = []
for i in range(N):
    #print(left, mid, right)
    n = int(input())
    if i == 0:
        mid = n
    elif i == 1:
        if n >= mid:
            heapq.heappush(right, n)
        else:
            heapq.heappush(left, -n)
    else:
        if n >= mid:
            if right:
                r = heapq.heappop(right)
                if r >= n:
                    heapq.heappush(left, -mid)
                    mid = n
                else:
                    heapq.heappush(right, n)
                heapq.heappush(right, r)
            else:
                heapq.heappush(right, n)
        else:
            if left:
                l = -(heapq.heappop(left))
                if l <= n:
                    heapq.heappush(right, mid)
                    mid = n
                else:
                    heapq.heappush(left, -n)
                heapq.heappush(left, -l)
            else:
                heapq.heappush(left, -n)
    #print(left, mid, right)
    answer.append(mid)


for i in answer:
    print(i)

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

문제

문제

출처

ICPC

어떤 논리상의 문제가 있는지 모르겠습니다.

2000flora 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말