[프로그래머스] 코딩테스트 연습 - 이중우선순위큐 풀이 (파이썬)
문제
- 요약
| 명령어 | 수신 탑(높이) |
| I 숫자 | 큐에 숫자 삽입 |
| D 1 | 큐에서 최댓값 삭제 |
| D -1 | 큐에서 최솟값 삭제 |
모든 연산 수행 후 큐가 비어있으면 [0, 0], 아니면 [최댓값, 최솟값] return
- 제한사항
: operations 의 길이 : 1 ~ 1,000,000
: operations 의 원소 : "명령어 데이터" 의 형식 - 연산에서 최댓값/최솟값이 둘 이상일 경우 하나만 삭제
: 빈 큐에 데이터 삭제 연산 - 무시
- 입출력 예시
| operations | return |
| ["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"] | [0,0] |
| ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"] | [333, -45] |
- 설명
: 문제에서 요구한 사항들을 차례대로 구현하면 되는 문제라고 판단
0. 자료를 담기 위한 구조 정의 : double_queue (리스트와 데크로 시험해 보았다.)
1. operations의 각 원소들에 대해 for loop를 사용
2. '명령어' '데이터'의 형태로 가공하기 위해, .split()을 활용하여 데이터 변환
3. '명령어' 별 기능 구현
3-1. 'I' : 숫자 삽입
3-2. 'D' : '1', '-1'에 따라 각각 최소, 최댓값을 제거
: 단순하게 요구한 사항들을 구현하였더니, 6개의 테스트케이스 중 2개만 맞고, 처음에는 런타임 에러가 발생하였다.
아무래도 제한시간을 초과한 것 같다고 판단하여, "D"의 연산을 실행하기 위한 분기점으로, 자료를 담은 구조(double_queue)의 길이가 0이 아닐 경우에만 실행이 되게 변경해 주니, 런타임 에러는 사라졌으며, 대신 1개의 테스트 케이스를 추가적으로 맞췄다.
이후, 제한사항을 토대로 테스트 케이스를 추가해보니, double_queue가 for loop 내부에 들어있어서 모든 원소가 삭제되면 다음 연산을 수행하지 않고 바로 [0, 0]을 반환해 주는 것을 파악할 수 있었고, 최종적으로 문제를 맞췄다.
- 제한사항 검증을 위한 테스트 케이스 추가
- 나의 풀이
from collections import deque
def solution(operations):
double_queue = deque()
# double_queue = []
for operation in operations :
operation = operation.split()
# print(operation)
if operation[0] == "I" :
double_queue.append(int(operation[1]))
elif len(double_queue)!= 0 : # "D" - 빈 큐에 삭제 : 무시
if operation[1] == '1':
double_queue.remove(max(double_queue))
else : # '-1'
double_queue.remove(min(double_queue))
# print(double_queue)
if len(double_queue) == 0 :
return [0, 0]
return [max(double_queue), min(double_queue)]고찰 : 문제를 처음에는 이중우선순위큐라고 주어져 있어, 별 다른 생각 없이 deque를 사용하여 구현하였는데, 이후 호기심이 생겨서 리스트로도 테스트를 진행해 보니, 일부 테스트케이스에서 소요 시간 과 메모리 용량이 감소하는 것을 확인할 수 있었다. 예상했던 경향과 달라서 흥미롭기는 한데, 왜 그런지는 자료형 클래스를 확인해봐야 할 것 같다 !
