절댓값 힙
시간 제한메모리 제한제출정답맞힌 사람정답 비율
| 1 초 (추가 시간 없음) (하단 참고) | 256 MB | 72489 | 41510 | 32592 | 57.246% |
문제
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
- 배열에 정수 x (x ≠ 0)를 넣는다.
- 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.
출력
입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
예제 입력 1 복사
18
1
-1
0
0
0
1
1
-1
-1
2
-2
0
0
0
0
0
0
0
예제 출력 1 복사
-1
1
0
-1
-1
1
1
-2
2
0
내친 김에 절댓값 힙도 조져보자...
다른 점은
아까 최소힙, 최대힙 문제는 0보다 큰 수만 들어오지만 이 친구는 정수가 다 들어온다는 거다.
글고 가장 작은 절댓값을 가진 애를 방출!!!!!
그러면 그 조건을 수정해야겠다 콜렉션... 예전에 Comparator로 순서 구현했었는데 아마 얘를 쓰는 거겠지?!!!
문법을 몰라서 좀 찾아보긴 했다.
Comparator -1.. 그냥 원래대로 0 같다 1 뒤집기....!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int x;
// 절댓값 기준으로 정렬되는 PriorityQueue를 생성 (Comparator 사용)
PriorityQueue<Integer> absHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(int x1, int x2) {
int tmpX1 = x1;
int tmpX2 = x2;
if (x1 < 0) {
int tmpX1 = x1 * -1;
} // 음수면 양수로 바꿔줌
if (x2 < 0) {
int tmpX2 = x2 * -1;
}
if (tmpX1 < tmpX2) {
return -1;
}
if (tmpX1 > tmpX2) {
return 1;
}
// 절댓값 똑같으면 작은 값이 앞으로
if (X1 < X2) {
return -1;
} else {
return 1;
}
}
});
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
x = Integer.parseInt(br.readLine());
if (x != 0) {
absHeap.offer(x);
continue;
} // 0 아니면 큐에 넣기
if (absHeap.isEmpty()) {
sb.append(0).append("\n");
continue;
} // 0인데 비어있을 때 -> sb에 0 추가
sb.append(absHeap.poll()).append("\n"); // 0이고 값 있을 때 값 빼내기
}
System.out.println(sb);
}
}
오ㅏ이러노...
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int x;
// 절댓값 기준으로 정렬되는 PriorityQueue를 생성 (Comparator 사용)
PriorityQueue<Integer> absHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer x1, Integer x2) {
int tmpX1 = x1;
int tmpX2 = x2;
if (x1 < 0) {
tmpX1 = x1 * -1;
} // 음수면 양수로 바꿔줌
if (x2 < 0) {
tmpX2 = x2 * -1;
}
// 왼쪽 거가 작으면 그대로
if (tmpX1 < tmpX2) {
return -1;
}
if (tmpX1 > tmpX2) {
return 1;
}
// 절댓값 똑같으면 작은 값이 앞으로
if (x1 < x2) {
return -1;
} else {
return 1;
}
}
});
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
x = Integer.parseInt(br.readLine());
if (x != 0) {
absHeap.offer(x);
continue;
} // 0 아니면 큐에 넣기
if (absHeap.isEmpty()) {
sb.append(0).append("\n");
continue;
} // 0인데 비어있을 때 -> sb에 0 추가
sb.append(absHeap.poll()).append("\n"); // 0이고 값 있을 때 값 빼내기
}
System.out.println(sb);
}
}
변수 재선언한 거랑 실수로 대문자 쓴 거 고치니까 됐다!
그치만
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int x;
// 절댓값 기준으로 정렬되는 PriorityQueue를 생성 (Comparator 사용)
PriorityQueue<Integer> absHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer x1, Integer x2) {
// 절댓값을 먼저 비교
int absX1 = Math.abs(x1);
int absX2 = Math.abs(x2);
if (absX1 < absX2) {
return -1; // x1의 절댓값이 더 작으면 x1이 먼저 오도록
}
if (absX1 > absX2) {
return 1; // x2의 절댓값이 더 작으면 x2가 먼저 오도록
}
// 절댓값이 같으면 더 작은 값이 먼저 오도록
return Integer.compare(x1, x2);
}
});
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
x = Integer.parseInt(br.readLine());
if (x != 0) {
absHeap.offer(x); // 0이 아니면 큐에 추가
} else {
if (absHeap.isEmpty()) {
sb.append(0).append("\n"); // 큐가 비어 있으면 0 출력
} else {
sb.append(absHeap.poll()).append("\n"); // 절댓값이 가장 작은 값을 출력하고 제거
}
}
}
System.out.print(sb);
}
}
Math 함수를 쓰면 더 편하게 구현 가능하다....... 네
'백준 풀기' 카테고리의 다른 글
| 백준 18352번: 특정 거리의 도시 찾기 with Java (0) | 2025.06.29 |
|---|---|
| 백준 2075번: N번째 큰 수 with Java (0) | 2025.06.22 |
| 백준 11279번: 최대 힙 with Java (0) | 2025.06.21 |
| 백준 1927번: 최소 힙 with Java (0) | 2025.06.21 |
| 백준 10819번: 차이를 최대로 with Java (2) | 2025.06.15 |