
✔ 문제 014 절댓값 힙 구현하기
⬜ 핵심 아이디어
- x = 0 일때
- 큐가 비어있을때는 0을 출력
- 비어 있지 않을때는 절댓값이 최소인 값을 출력. 절댓값이 같다면 음수를 우선하여 출력
- x = 1 일때
- add로 큐에 새로운 값을 추가하고 우선순위 큐 정렬 기준으로 자동 정렬
TIP : 람다함수에서 정렬 헷갈린다면, 양수면 첫번째(o1)가 뒤로.음수면 두번째(o2)가 뒤로 간다고 생각하면쉽다.
PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2)->{
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
if(first_abs == second_abs) {return o1 > o2 ? 1 : -1;} // 절댓값이 같으면 음수 우선 정렬
else {return first_abs - second_abs;} // 절댓값 기준 정렬
});
슈도코드 작성하기
N(질의 요청 개수)
우선순위 큐 선언
- 절댓값 기준으로 정렬되도록 설정
- 단, 절댓값 같으면 음수 우선 정렬하기
for(N만큼 반복)
{
요청 0일때: 큐가 비어 있으면 0, 비어 있지 않으면 큐의 front 값 출력하기(poll())
요청 1일때: 새로운 데이터를 우선순위 큐에 더하기 (add())
}
JAVA
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;
class Main {
public static void main (String[] args) throws java.lang.Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 연산개수
PriorityQueue<Integer> MyQueue = new PriorityQueue<>((o1, o2)->{
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
if(first_abs == second_abs) {return o1 > o2 ? 1 : -1;} // 절댓값이 같으면 음수 우선 정렬
else {return first_abs - second_abs;} // 절댓값 기준 정렬
});
for(int i = 0; i < N; i++){
int request = Integer.parseInt(br.readLine());
if(request == 0) { // 출력
if(MyQueue.isEmpty()) {System.out.println("0");}
else {System.out.println(MyQueue.poll());}
} else{ // 0 아니면 add
MyQueue.add(request);
}
}
}
}
PYTHON
import sys, heapq
abs_heap = []
N = int(sys.stdin.readline())
for i in range(N):
num = int(sys.stdin.readline())
if num: # 출력 X,삽입
heapq.heappush(abs_heap, (abs(num), num))
else: # 출력
if abs_heap:
print(heapq.heappop(abs_heap)[1])
else:
print(0)'자료구조&알고리즘 > 알고리즘_코딩테스트' 카테고리의 다른 글
| [알고리즘_코딩 테스트_JAVA] 버블 소트 프로그램 1 (JAVA, PYTHON) (0) | 2024.01.01 |
|---|---|
| [알고리즘_코딩 테스트_JAVA] 수 정렬하기 1 (JAVA, PYTHON) (0) | 2023.12.27 |
| [알고리즘_코딩 테스트_JAVA] 카드 게임 (JAVA, PYTHON) (0) | 2023.12.26 |
| [알고리즘_코딩 테스트_JAVA] 오큰수 (JAVA, PYTHON) (1) | 2023.12.25 |
| [알고리즘_코딩 테스트_JAVA] 투 포인터 (JAVA, PYTHON) (1) | 2023.11.13 |