[파이썬 익숙해지기] no7662: 이중 우선순위 큐 - Heap 트리 및 입출력연습

문제

이 문제의 경우, 이전에 Java를 이용해 풀었던 문제지만, 평가기준 변경으로 다시 도전하게 된 문제이다.

(평가기준 변경으로, 이전의 자바코드로는 통과되지 않는다.)

# 1. 입력이 I n일경우, n을 add
# 2. 입력이 D 1일경우, 최대값 삭제
# 3. 입력이 D -1일경우, 최소값 삭제
# 4. 만약 Q가 비어있는 경우, D 연산은 무시
# 5. 모든 연산이 끝나고, 만약 Q가 비어있으면 Empty출력
# 6. 숫자가 남아있으면 최대값과 최소값을 출력

이전 링크 : https://radpro.tistory.com/513

문제 링크 : https://www.acmicpc.net/problem/7662

---

원리

힙(Heap)

1. 구조 : 완전 이진 트리의 일종으로서, 우선순위 큐를 위해 만들어진 자료구조

2. 특징 :
 2-1) 반정렬상태(느슨한 정렬 상태)로서, 부모노드의 키 값이 자식노드의 키 갑보다 항상 큰(작은)값을 가지는 이진트리

 2-2) 힙트리는 중복값이 허용 (이진 탐색 트리에서는 중복값 미허용)

3. 사용 :  최소힙/최대힙

 

파이썬에서의 힙 (Heap for use with Python)

1. 단, 파이썬의 힙 트리는 최소힙만 지원하므로, 최대힙을 따로 구현해주어야 한다.

2. 최대힙/최소힙을 동기화 시켜주어야 한다.

 

---

학습 내용

1. deque

: Java에서 주로 사용하던 deque가 파이썬에도 있었다. (collection이 파이썬에도 있었다.)

import deque from collection

append(입력값)  # 입력
pop(출력인덱스)  # 출력
sort()  # 정렬
reverse()  # 배열뒤집기

2. 부정 조건문 (부정문, !=)

: Java에선 조건에 !를 붙여 사용했지만, 파이썬의 경우 다르다.

Java에서의 if(!true) {}와 같은 방식

if not (true) :

3. 파이썬 타입은 자동으로 형변환 되지 않는다.

: 즉, 아래와 같이 사용한다면 타입에러가 발생한다.

A = int(input())  # int 타입
B = input()  # str 타입

print(A + B)  # => int에 str을 붙일 수 없기에 타입에러 발생

올바른 출력이 되려면 다음 중 하나여야 한다.

print(str(A) + B)
또는
print(A + int(B))

 

4. 파이썬의 입력

한 두중 입력받는 경우가 아닌, 다수의 입력을 받는 경우 input()함수를 사용하면 메모리 소모가 심하다.

따라서 sys 라이브러리를 이용해 아래 함수로 입력을 받는다.

단, str타입으로 받을 경우, 개행문자 \n이 함께 받아진다.

0. 라이브러리 추가
import sys


1. 문자열을 입력받는 경우
a = sys.stdin.readline()  # alpha 입력시, alpha\n출력

2. 한 개의 정수를 입력받는 경우
a = int(sys.stdin.readline())

3. 정해진 개수의 정수를 한 줄에 입력받을 때
a,b,c = map(int,sys.stdin.readline().split())

4. 임의 개수의 정수를 한 줄에 입력받아 리스트에 저장할 때
data = list(map(int, sys.stdin.readline().split()))

5. 임의 개수의 정수를 n줄 입력받아 2차원 리스트에 저장할 때
data = []
n = int(sys.stdin.readline())
for i in range(n):
    data.append(list(map(int,sys.stdin.readline().split())))
    
6. N줄의 문자열을 입력받아 리스트에 저장할 때
n = int(sys.stdin.readline())
data = [sys.stdin.readline().strip() for i in range(n)]

 

---

나의 코드

[파이썬 코드] 하드코딩

from collections import deque  

T = int(input())

for i in range(0, T) :
    N = int(input())
    Q = []
    for j in range(0, N) :
        A, B = input().split()
        B = int(B)
        if(A=="I"):
            Q.append(B)
        elif (B == 1) :
            if (Q) :
                Q.sort()
                Q.reverse()
                Q.pop(0)
        else :
            if (Q) :
                Q.sort()
                Q.pop(0)
    if(Q) :
        Q.sort()
        Q.reverse()
        result1= Q.pop(0)
        Q.sort()
        print (str(result1) + " " + str(Q.pop(0)))
    else :
        print("Empty")

 

[파이썬 Heap트리 코드]

import sys
import heapq

for T in range (int (sys.stdin.readline())) : # 테스트 케이스만큼 반복할 것
    k = int(sys.stdin.readline())   # 각 테스트 케이스마다 k줄만큼 입력이 있을 것
    visited = [False] * k  # 각 입력 수만큼 방문체크하기위한 리스트(배열) 생성
    maxHeap, minHeap = [], []

    for i in range(k) :
        operation, n = sys.stdin.readline().split()  # 입력된 명령어(I/D)와 숫자n을 " "을 기준으로 분리해 저장
        n = int(n)

        if operation == 'I' :
            heapq.heappush(minHeap, (n, i))  # 최소힙을 만들어줄 리스트에, 인덱스에 맞춰 순차적으로 n값을 넣어줌
            heapq.heappush(maxHeap, (-n, i))  # 최대힙을 만들어줄 리스트에, 인덱스에 맞춰 순차적으로 n값을 반전시켜 넣어줌
            visited[i] = True

        elif n == 1 :  # I가 아닌경우는 무조건 1 또는 -1의 경부밖에 없기 때문
            while maxHeap and not visited[maxHeap[0][1]]:
                heapq.heappop(maxHeap)
            if maxHeap :  # maxHeap이 비어있지 않을 때
                visited[maxHeap[0][1]] = False
                heapq.heappop(maxHeap)

        else :  # D이고 -1일 때
            while minHeap and not visited[minHeap[0][1]]:
                heapq.heappop(minHeap)
            if minHeap:
                visited[minHeap[0][1]] = False
                heapq.heappop(minHeap)

    while minHeap and not visited[minHeap[0][1]]:
        heapq.heappop(minHeap)
    while maxHeap and not visited[maxHeap[0][1]]:
        heapq.heappop(maxHeap)

    # 최대힙은 값을 반전시킨 최소힙으로 되어있으므로, 출력 전에 -를 곱해서 반전 시켜준 뒤 출력
    if maxHeap and minHeap:
        print(-maxHeap[0][0], minHeap[0][0]) 
    else: 
        print("EMPTY")

---

레퍼런스

레퍼런스 코드 : https://codio.tistory.com/entry/%EB%B0%B1%EC%A4%80-7662%EB%B2%88-%EC%9D%B4%EC%A4%91-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-Python%ED%8C%8C%EC%9D%B4%EC%8D%AC