[Baekjoon/Java] 11286번 절댓값 힙

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

 

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

문제 풀이

 

첫번째 풀이 - 맞았습니다!!

한 번에 맞추면 기분이 좋다 ㅎ PriorityQueue를 써야 한다는 건 알았지만 어떻게 양수와 음수를 구별해야하는지는 고민이 됐다. 객체를 넣어야겠다고 생각은 했지만 우선 순위를 어떻게 구현해야할지는 감이 안 잡혔다. 그래서 이 부분은 검색을 통해 배웠다.

 

일단 나는 NumComparator 클래스를 정의했다. 이는 우선순위 큐 내부적으로 객체를 비교할 때 compare() 메서드를 override하여 비교 기준을 정한다.

 

나는 객체에서 num은 입력 받는 숫자, isPlus는 양수 값이라면 1, 음수 값이라면 0을 입력하도록 했다.

원래는 boolean으로 하고싶었는데 그러면 어떻게 비교하는거지..? 라는 고민에 빠져 int로 바꿨다.

 

그리고 처음엔 num을 비교해서 더 작은 수로 정렬을 하고 만약 num이 같다면 isPlus를 비교하며 더 작은값을 먼저 정렬시켰다.

 

다행히 내가 생각했던 로직이 맞아서 한 번에 통과했다. 요즘 알고리즘 풀 때 들이는 습관으로 다른 사람과의 메모리, 시간을 비교해보고 나보다 적은 메모리, 적은 시간이 나온 사람의 코드를 훑어본다. 근데 왜인걸 위의 사진에 보다시피 메모리가 93780KB 로 다른 사람의 2~3배였다. 다른 사람들은 다 20000~50000KB 사이던데 너무 많은 차이가 나서 코드를 살펴봤는데 굳이 클래스를 정의하지 않고 priorityQueue 자체에서 정렬하도록 했다. 나는 혹시나 내가 Scanner로 입력 받는게 많은 메모리를 사용한 이유가 아닐까 싶어서 입력을 BufferedReader로 바꿨고 다른 사람들보다 메모리, 시간적인 측면에서 월등히 낮은 숫자를 기록해서 뿌듯했다.ㅎㅎ

 

코드

1. 입력 방법 : Scanner

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	public static class Node{
		int num;
		int isPlus;
		
		public Node(int num, int isPlus) {
			this.num = num;
			this.isPlus = isPlus;
		}
	}
	
	public static class NumComparator implements Comparator<Node> {
		@Override
		public int compare(Node o1, Node o2) {
			if(o1.num == o2.num) {
				return o1.isPlus - o2.isPlus;
			}else {
				return o1.num - o2.num;
			}
		}	
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PriorityQueue<Node> queue = new PriorityQueue<>(new NumComparator());
		StringBuilder sb = new StringBuilder();
		
		int N = sc.nextInt();
		for(int i=0; i<N; i++) {
			int num = sc.nextInt();
			
			if(num == 0) {
				if(!queue.isEmpty()) {
					Node tmp = queue.remove();
					if(tmp.isPlus == 1) {
						sb.append(tmp.num).append("\n");					
					}else {
						sb.append(-tmp.num).append("\n");
					}
				}else {
					sb.append(0).append("\n");
				}
				
			}else if(num > 0){
				queue.add(new Node(num, 1));
			}else if(num < 0) {
				queue.add(new Node(-num, 0));
			}
		}
		System.out.println(sb);
	}
}

 

2. 입력 방법 : BufferedReader

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	public static class Node{
		int num;
		int isPlus;
		
		public Node(int num, int isPlus) {
			this.num = num;
			this.isPlus = isPlus;
		}
	}
	
	public static class NumComparator implements Comparator<Node> {
		@Override
		public int compare(Node o1, Node o2) {
			if(o1.num == o2.num) {
				return o1.isPlus - o2.isPlus;
			}else {
				return o1.num - o2.num;
			}
		}	
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PriorityQueue<Node> queue = new PriorityQueue<>(new NumComparator());
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(br.readLine());
			
			if(num == 0) {
				if(!queue.isEmpty()) {
					Node tmp = queue.remove();
					if(tmp.isPlus == 1) {
						sb.append(tmp.num).append("\n");					
					}else {
						sb.append(-tmp.num).append("\n");
					}
				}else {
					sb.append(0).append("\n");
				}
				
			}else if(num > 0){
				queue.add(new Node(num, 1));
			}else if(num < 0) {
				queue.add(new Node(-num, 0));
			}
		}
		System.out.println(sb);
	}
}

 

새롭게 알게 된 점

public static class NumComparator implements Comparator<Node> {
    @Override
    public int compare(Node o1, Node o2) {
        if(o1.num == o2.num) {
            return o1.isPlus - o2.isPlus;
        }else {
            return o1.num - o2.num;
        }
    }
}

 

Comparator를 상속 받아서 compare 메서드를 재정의하는 방법은 아직 익숙하지가 않다. 앞으로도 많이 쓰일 것 같으니까 정리해두고 기억해둬야겠다.

 

느낀점

PriorityQueue를 사용하는걸 미루기만 해왔었는데 막상 풀어보니 앞으로 많이 사용할 것 같고 앞으로도 계속 새로운 것들을 배워나가면서 알고리즘 실력을 많이 키우고싶다. ㅎ

 

 

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙