7662

편집 시간: 2022년 2월 16일 오후 4:02

코드

Algorithm/7662.py at main · Junroot/Algorithm

풀이

실패한 풀이: Node 클래스 만들기

최대 힙과 최소 힙을 두 개 마련해두고, 삭제 될 때 해당 숫자가 삭제되었다고 표시만 하면되기 때문에, 힙의 각 노드들을 아래와 같이 클래스로 만들어 deleted 필드를 두려고했다.

class Node:
	def __init__(self, data):
		self.data = data
		self.deleted = False

하지만 한 가지 문제가 있었다. heapq 라이브러리는 최대 힙을 만들 수 없다. 그래서 일반적인 힙 문제에서는 음수를 취하여 힙에 추가하는데 현재는 최소 힙과 최대 힙이 노드를 공유하고 있어야되기 때문에 불가능하다.

성공한 풀이: 해쉬 맵 사용하기

현재 이중순위 큐에 각 숫자가 몇 개씩 남아 있는지 확인하기 위해서 해쉬 맵을 하나 만들었다. 만약 pop을 할 때 해쉬 맵에 현재 숫자의 개수가 0이라면 새로 하나 pop을 하여 반환해야 된다.