글 읽기 - 제 알고리즘에 틀린 부분이 있을까요?

shanytt 4년 전 0

안녕하세요, 아래와 같은 알고리즘을 작성해서 구현했는데

틀렸습니다 가 나와서 알고리즘에 문제가 있는지 의견을 여쭤보려고 질문드립니다.

알고리즘

1. maxheap, minheap을 만들고, deleted_from_min, deleted_from_max 라는 Counter 를 만듭니다

(Counter는 python dictionary와 같은데 value가 0이 되면 key를 삭제하는 자료구조입니다.)

2. Insert 쿼리가 들어오면 maxheap, minheap에 모두 넣습니다.

3. 최대값을 지우는 쿼리가 들어오면, maxheap의 최대값을 꺼냅니다.

3-1. 그 값을 item이라고 하면, item이 deleted_from_min의 key로 존재하는지 확인합니다. 있다면 deleted_from_min[item]의 value를 1 줄이고, 3을 반복합니다.

3-2. key로 존재하지않는다면 deleted_from_max[item] 을 1 늘려줍니다

4. 최솟값을 지우는 쿼리가 들어오면, 위와 정반대로 합니다.

5. 모든 쿼리에 대해 2~4를 반복합니다.

6. maxheap의 최대값이 deleted_from_min 에 존재한다면 제거하고 다음 값을 확인합니다. deleted_from_min에 없는 값이 나올 때까지 반복합니다. 마지막으로 확인한 값이 최대값입니다.

7. 마찬가지로 minheap에 대해서도 반복합니다. 마지막으로 확인한 값이 최소값입니다.

최대한 풀어서 작성했는데 잘 이해가 되셨을지 모르겠네요.

혹시 이 알고리즘이 동작 안 하는 반례가 있을까요?

감사합니다.

import heapq
import collections
import sys
input = sys.stdin.readline

# Init
def solve():
    min_heap = []
    max_heap = []

    deleted_from_min = collections.defaultdict(int)
    deleted_from_max = collections.defaultdict(int)

    k = int(input())
    for _ in range(k):
        query, param = input().split()
        param = int(param)

        if query == 'I':
            heapq.heappush(min_heap, param)
            heapq.heappush(max_heap, -param)
        elif param == 1:
            # delete from max_heap
            if max_heap:
                item = -heapq.heappop(max_heap)
                empty = False
                while item in deleted_from_min:
                    deleted_from_min[item] -= 1
                    if deleted_from_min[item] == 0:
                        del deleted_from_min[item]

                    if not max_heap:
                        empty = True
                        break
                    item = heapq.heappop(max_heap)

                if not empty:
                    deleted_from_max[item] += 1
        else:
            #delete from min_heap
            if min_heap:
                item = heapq.heappop(min_heap)
                empty = False
                while item in deleted_from_max:
                    deleted_from_max[item] -= 1
                    if deleted_from_max[item] == 0:
                        del deleted_from_max[item]

                    if not min_heap:
                        empty = True
                        break
                    item = heapq.heappop(min_heap)

                if not empty:
                    deleted_from_min[item] += 1

    def finalize():
        if not min_heap:
            print('EMPTY')
            return

        while max_heap and -max_heap[0] in deleted_from_min:
            item = -heapq.heappop(max_heap)
            deleted_from_min[item] -= 1
            if deleted_from_min[item] == 0:
                del deleted_from_min[item]
        if not max_heap:
            print('EMPTY')
            return

        while min_heap and min_heap[0] in deleted_from_max:
            item = heapq.heappop(min_heap)
            deleted_from_max[item] -= 1
            if deleted_from_max[item] == 0:
                del deleted_from_max[item]

        print(-max_heap[0], min_heap[0])
    finalize()

t = int(input())
for _ in range(t):
    solve()

unused 4년 전 2

35번째 라인 맞나요?

shanytt 4년 전 0

35번째 라인을 item = -heapq.heappop(max_heap) 로 수정해서 해결했습니다.

도움주셔서 정말 감사합니다.

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