[ Programmers 42628 ] 이중우선순위큐 (Python)

uoayop·2021년 6월 7일
0

알고리즘 문제

목록 보기
97/103
post-thumbnail

문제

https://programmers.co.kr/learn/courses/30/lessons/42628

우선순위큐는 나야~ 둘이 될 수 없어~


문제 풀이

이중.. 큐라고 되어있어서 처음에 힙을 두개 써서 문제를 풀려고 했다.
최소 힙, 최대 힙 두 개 써서 중앙값을 구하는 문제처럼 풀고 싶었는데 마음같이 잘 안됐다.,, 😇

그래서 bisect로 풀어보았다.

from bisect import bisect_left

bisect_left는 요소가 삽입 될 위치를 찾아준다.

( bisect를 이용해서 푼 문제 - BOJ 12015 )


1. 명령어가 I 일 경우

for row in operations:
    opr, num = row.rsplit()
    if opr == 'I':
        index = bisect_left(answer, int(num))
        answer.insert(index, int(num))

bisect를 이용해서 answer 리스트의 적절한 위치에 삽입해주었다.

2. 명령어가 D 일 경우

    else:
        if answer:
           if num == '1':
                del answer[-1]
           else:
                del answer[0]

리스트가 비어있지 않을 때 숫자에 따라 리스트에서 최대값이나 최소값을 삭제한다.

3. 출력하기

if answer:
    return [answer[-1], answer[0]]
else:
    return [0, 0]

모든 연산이 끝나고 리스트가 비어있으면 [0, 0] 출력
리스트에 값이 남아있으면 [최대값, 최소값] 출력


코드

from bisect import bisect_left

def solution(operations):
    answer = []

    for row in operations:
        opr, num = row.rsplit()
        if opr == 'I':
            index = bisect_left(answer, int(num))
            answer.insert(index, int(num))
        else:
            if answer:
                if num == '1':
                    del answer[-1]
                else:
                    del answer[0]

    if answer:
        return [answer[-1], answer[0]]
    else:
        return [0, 0]
profile
slow and steady wins the race 🐢

0개의 댓글