코딩 테스트에서 자주 등장하는 문제 중 하나는 데이터를 효율적으로 저장하고 관리하는 자료구조의 구현입니다. 본 글에서는 절댓값 힙(absmin heap)이라는 자료구조에 대해 설명하고, 자바를 이용하여 이를 구현하는 방법을 알아보겠습니다. 절댓값 힙은 입력 데이터의 절댓값을 기준으로 우선순위를 정하는 힙입니다.
문제 설명
주어진 정수 리스트에 대해 절댓값 힙을 구현하는 문제입니다. 절댓값 힙은 다음과 같은 기능을 지원해야 합니다:
- 절댓값이 가장 작은 값을 제거하고 그 값을 반환하는 기능
- 주어진 정수를 절댓값 힙에 추가하는 기능
구현되는 절댓값 힙의 작동 방식은 다음과 같습니다:
- 절댓값이 작은 순서로 원소들이 정렬된다.
- 절댓값이 같을 경우, 원래 값이 더 작은 원소가 더 우선시 된다.
입출력 형식
입력은 다음과 같은 형식으로 주어집니다:
N
operation[0]
operation[1]
...
operation[N-1]
여기서 N은 연산의 수이며, 각 operation[i]는 다음과 같습니다:
0: 절댓값 힙에서 가장 작은 값을 제거하고 출력하십시오.- 기타 정수
x: 절댓값 힙에x를 추가하십시오.
예제
입력
7
5
3
6
0
-2
4
0
출력
-2
3
위의 예제에서는 다음과 같은 과정을 따릅니다:
- 5, 3, 6를 추가하면 힙에 [5, 3, 6]이 저장됩니다.
- 0을 주면 가장 작은 절댓값인 -2가 나옵니다.
- 또한, 절댓값이 가장 작은 3이 출력됩니다.
절댓값 힙 구현 과정
이제 절댓값 힙을 자바로 구현해 보겠습니다. 기본적으로, 자바에서는 PriorityQueue를 사용하여 힙을 구현할 수 있습니다. 그러나 이 경우에는 절댓값을 기준으로 우선순위를 설정해야 하므로, 다음과 같이 Comparator를 작성합니다.
1단계: 힙 노드 정의
힙에서 저장할 데이터 구조체를 만듭니다. 여기서 각 숫자의 원래 값과 절댓값을 저장할 것입니다.
class AbsHeapNode {
int value;
public AbsHeapNode(int value) {
this.value = value;
}
public int getAbs() {
return Math.abs(value);
}
}
2단계: Comparator 정의
절댓값으로 비교할 수 있는 Comparator를 정의합니다.
class AbsMinComparator implements Comparator<AbsHeapNode> {
@Override
public int compare(AbsHeapNode a, AbsHeapNode b) {
if (a.getAbs() != b.getAbs()) {
return Integer.compare(a.getAbs(), b.getAbs());
}
return Integer.compare(a.value, b.value);
}
}
3단계: 절댓값 힙 구현
이제 실제 절댓값 힙을 구현하는 클래스를 생성합니다.
import java.util.PriorityQueue;
public class AbsHeap {
private PriorityQueue<AbsHeapNode> heap;
public AbsHeap() {
heap = new PriorityQueue<>(new AbsMinComparator());
}
public void insert(int value) {
heap.offer(new AbsHeapNode(value));
}
public Integer removeMin() {
AbsHeapNode node = heap.poll();
return (node != null) ? node.value : null;
}
}
4단계: 메인 메소드 구현
앞서 구현한 클래스들을 사용하여 메인 메소드를 작성합니다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
AbsHeap absHeap = new AbsHeap();
int N = scanner.nextInt();
for (int i = 0; i < N; i++) {
int operation = scanner.nextInt();
if (operation == 0) {
Integer minValue = absHeap.removeMin();
System.out.println(minValue != null ? minValue : 0);
} else {
absHeap.insert(operation);
}
}
scanner.close();
}
}
결론
절댓값 힙을 구현하는 과정에서는 상황에 맞는 Comparator를 정의하는 것이 매우 중요합니다. 이를 통해 부여받은 문제를 해결할 수 있는 효율적인 자료구조를 구축할 수 있었습니다. 코딩 테스트에서 이와 같은 문제는 비슷한 형태의 알고리즘 질문으로 자주 출제되므로, 충분한 연습을 통해 숙달하는 것이 중요합니다. 앞으로도 다양한 알고리즘과 자료구조를 연습하여 더 나은 프로그래머가 되시기 바랍니다. 감사합니다!