[프로그래머스] 코딩테스트 연습 - 이중우선순위큐 풀이 (파이썬)

문제

- 요약

명령어	수신 탑(높이)
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를 사용하여 구현하였는데, 이후 호기심이 생겨서 리스트로도 테스트를 진행해 보니, 일부 테스트케이스에서 소요 시간 과 메모리 용량이 감소하는 것을 확인할 수 있었다. 예상했던 경향과 달라서 흥미롭기는 한데, 왜 그런지는 자료형 클래스를 확인해봐야 할 것 같다 !

deque로 실행 시 결과

list로 실행 시 결과