[백준 7662번-이중 우선순위 큐]-파이썬

solved.ac 난이도 : GOLD5

백준  7662번- 파이썬 풀이

 

<문제>

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

<풀이>-자료구조, 우선순위 큐, 트리를 사용한 집합과 맵

이 문제는 두 배열을 어떻게 동기화 시켜주는지가 관건이다. 

 

우선순위 큐에 대한 내용은 아래에 링크를 참고하면 이해하기 편할 것이다.

https://hae-sooo97.tistory.com/22?category=925334

우선순위 큐( heapq)

우선 크게 큐에 삽입하는 부분과 삭제하는 부분을 살펴보자

최소힙, 최대힙 두개를 동시에 구현하기 위해 배열을 두가지 선언해준다.

 

-큐에 삽입하는 부분-

 

큐에 삽입할때 중요한것은 나중에 삭제할때를 대비해 다른 큐에서 삭제되었는지 아닌지를 판단할 수 있도록 삽입하는것이 중요하다.

 

따라서 큐에 삽입할때 visitied=True로 해주어 숫자와 True 두가지를 삽입해준다.

 

    visitied = [False]*1000001
    min_heap,max_heap = [],[]
    for i in range(k):
        order,number = input().split()
        if order == 'I':
            heapq.heappush(min_heap,(int(number),i))
            heapq.heappush(max_heap,(-int(number),i))
            visitied[i] = True

 

-큐에서 삭제하는 부분-

 

우선 최소힙에서 삭제하는 부분부터 살펴보자

 

큐에 삽입할때 visitied  = True로 해주었으므로 큐에서 삭제를 해준다음 visitied를 False 상태로 되돌려놓는다.

 

근데 만약 최소힙에 남아있는 원소가 최대힙에서는 삭제된 것이라면 그 원소의 visitied값은 False일것이다.

 

따라서 최소힙에 있는 visitied가 False인 원소를 모두 삭제해준다.

 

최대힙을 구현할때도 위와 같은 과정을 똑같이 반복한다.

 

      
            #최소힙구현
            if number == "-1":
                #큐에 들어있고 visitied가 False라면 max_heap에서 삭제된 원소
                while min_heap and not visitied[min_heap[0][1]]:
                    heapq.heappop(min_heap)
                if min_heap: #큐에 들어있는경우(visited = True)
                    visitied[min_heap[0][1]] = False
                    heapq.heappop(min_heap)

<코드>-파이썬

728x90

반응형

import heapq
t = int(input())
for _ in range(t):
    k = int(input())
    visitied = [False]*1000001
    min_heap,max_heap = [],[]
    for i in range(k):
        order,number = input().split()
        if order == 'I':
            heapq.heappush(min_heap,(int(number),i))
            heapq.heappush(max_heap,(-int(number),i))
            visitied[i] = True
        
        else:
            #최소힙구현
            if number == "-1":
                #큐에 들어있고 visitied가 False라면 max_heap에서 삭제된 원소
                while min_heap and not visitied[min_heap[0][1]]:
                    heapq.heappop(min_heap)
                if min_heap: #큐에 들어있는경우(visited = True)
                    visitied[min_heap[0][1]] = False
                    heapq.heappop(min_heap)
            #최대힙 구현
            if number == "1":
                #큐에 들어있고 visitied가 False라면 min_heap에서 삭제된 원소
                while max_heap and not visitied[max_heap[0][1]]:
                    heapq.heappop(max_heap)
                if max_heap:#큐에 들어있는 경우(visitied = True)
                    visitied[max_heap[0][1]] = False
                    heapq.heappop(max_heap)
    while min_heap and not visitied[min_heap[0][1]]:
        heapq.heappop(min_heap)
    while max_heap and not visitied[max_heap[0][1]]:
        heapq.heappop(max_heap)

    if len(min_heap)==0 or len(max_heap) == 0:
        print("EMPTY")
    else:
        print(-max_heap[0][0], min_heap[0][0])

모든 연산이 끝난 후에도 각각의 배열에 visitied은 False 인 상태로 남아있는 원소가 있을 수 있다. 

(만약 D=1인경우 밖에 없어 최대힙만 구현했다면 최소힙에는 최대힙에서 삭제된 원소가 그대로 남아있는다.)

 

따라서 다시 한번더 이러한 원소를 삭제해주는 과정을 반복한다음 최종결과를 출력한다.

 

 

-마치며-

 

문제를 처음 접할때 익숙했던 우선순위 큐에 대한 내용이라 자신이 있었지만 동기화 시켜주는 부분에서 애를 먹어 결국 풀이법을 찾아봤다. 이러한 방법이 있는지 확실하게 인지한다음 비슷한 문제를 만났을때 꼭 자기 힘으로 풀 수 있도록 연습하는것이 중요할 거 같다.