Link : programmers.co.kr/learn/courses/30/lessons/42628
1. 문제
- 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. - 명령어수신 탑(높이)
2. 문제의 조건
- 1 <= operations <= 1000000
- 삭제할 연산이 없을경우 삭제연산은 무시
더보기
3. 문제 접근
- 아이디어
문제 종류가 heap으로 되어있습니다. 자료구조를 이용하여 풀면 쉽게 풀 수 있는 문제입니다.
4. 풀이 방법
- 명령어와 수치로 나눕니다.
- 만약 추가명령이라면 heapq의 heappush를 이용해 값을 추가합니다. O(log N)
- 만약 삭제연산이라면 heap의 길이가 0보다 큰지 판단 후 크다면 삭제해줍니다.
이 때, 최대값의 삭제는 list의 pop으로 처리해줍니다 O(1)
최소값의 삭제는 heapq.heappop(heap)으로 해줍니다 O(log N) - 만약 heap의 크기가 0보다 크다면 heap의 최대값과 최소값을 리턴하고, 0이라면 [0, 0]을 리턴합니다.
5. 소스코드
cjw.git@gmail.com
'알고리즘 > programmers' 카테고리의 다른 글
68936: 쿼드압축 후 개수 세기 (0) | 2021.04.02 |
---|---|
72410: 신규 아이디 추천 (0) | 2021.03.24 |
64062: 징검다리 건너기 (0) | 2021.01.25 |
60059: 자물쇠와 열쇠 (0) | 2021.01.25 |
43164: 여행경로[DFS/BFS] (0) | 2021.01.14 |
댓글