728x90
반응형
문제:
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어 |
수신 탑(높이) |
I 숫자 |
큐에 주어진 숫자를 삽입합니다. |
D 1 |
큐에서 최댓값을 삭제합니다. |
D -1 |
큐에서 최솟값을 삭제합니다. |
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값,최솟값]을 return 하도록 solution 함수를 구현해주세요.
풀이 방법:
힙을 사용해서 풀어야 하는 문제지만 굳이 힙을 사용해서 풀지 않아도 상관 없다. operations를 반복문의 매개변수로 받아 각 원소들을 공백으로 구분해보아서 명령어대로 배열에서 처리를 하면 문제없이 풀 수 있다. 삽입을 할 때 정수형으로 변경을 해서 넣는데 그 이유는 음수값들도 들어가기 때문에 정렬을 하기 위해서는 정수형으로 바꾸는 것이 필수적이기 때문이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | def solution(operations): answer=[] for i in operations: a,b=i.split(" ") if a=="I": answer.append(int(b)) else: if len(answer)>0: if b=="1": answer.pop() else: answer.pop(0) else: pass answer.sort() if len(answer)==0: return [0,0] else: return [max(answer),min(answer)] | cs |
만약 힙을 사용해서 풀고 싶다면 다음과 같이 하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | import heapq def solution(operations): h=[] for i in operations: a,b=i.split(" ") if a=="I": heapq.heappush(h,int(b)) else: if len(h)>0: if b=="1": h.pop(h.index(heapq.nlargest(1,h)[0])) else: heapq.heappop(h) else: pass if len(h)==0: return [0,0] else: return [heapq.nlargest(1,h)[0],heapq.nsmallest(1,h)[0]] | cs |
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]Lv 2.올바른 괄호 (0) | 2019.03.04 |
|---|---|
| [Programmers]Lv 1. 체육복(테스트케이스 수정) (0) | 2019.03.03 |
| [Programmers]Lv 2.가장 큰 정사각형 찾기 (0) | 2019.03.02 |
| [Programmers]Lv 3. 입국 심사 (2) | 2019.03.01 |
| [Programmers]Lv 2. 타겟 넘버 (0) | 2019.02.28 |