백준 11286 java - 절댓값 힙

 

 

문제, 입출력, 테스트케이스

50분 타이머 기준 31분 14초가 남았다.

쉬운 문제지만 문제를 제대로 안 읽으면 이렇게 됩니다.jpg

해당 문제는 최소힙 + CompareTo를 통해 풀 수 있었다. 그리고 자료형의 중요성과 문제를 제대로 읽어야 한 다는 것을 번 깨달은 문제이다...

 

<문제 풀이/접근과정>
1. 배열에 정수 x (x ≠ 0)를 넣는다. 
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. -> 가장 작은 수를 출력하라고? 최소힙(우선순위큐)을 쓰면 되겠네
3. 1 <= N <= 100,000, x는 long 범위 -> long형 최소힙 선언
4. 절댓값 기준 그다음 원래 값 기준으로 최솟값을 빼내와야 하므로 Comparable 또는 CompareTo 재정의 필요 -> 따로 클래스 선언해서 써야겠다.
5. 자료형을 순간 2^32승이 int형 범윈 줄 알고 int형을 썼어서 틀렸고 절댓값이 같을 때를 처리 하지 않아서 계속 틀렸다. -> 이왜틀 시전

 

package boj;

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

public class Boj_11286 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 배열에 정수 x (x ≠ 0)를 넣는다.
		// 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를
		// 출력하고, 그 값을 배열에서 제거한다.
		// 1 <= N <= 100,000, x는 long 범위 -> long형 최소힙 선언

		PriorityQueue<Node> pq = new PriorityQueue<>();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			long temp = Long.parseLong(br.readLine());
			if (temp == 0) {
				if (pq.isEmpty()) {
					sb.append(temp).append("\n");
				} else {
					sb.append(pq.poll().origin).append("\n");
				}
			} else {
				pq.add(new Node(temp));
			}
		}
		sb.setLength(sb.length() - 1);
		System.out.println(sb);
	}

	static class Node implements Comparable<Node> {
		long origin;
		long absolute;

		public Node(long origin) {
			this.origin = origin;
			this.absolute = (long) Math.abs(origin);
		}

		@Override
		public int compareTo(Node o) {
			if (this.absolute == o.absolute) {
				return this.origin <= o.origin ? -1 : 1;
			}
			return this.absolute <= o.absolute ? -1 : 1;
		}

	}
}

실버 1인 이유를 모르겠는 문제이다 그냥 우선순위큐와 CompareTo 또는 Comparable 사용만 잘하면 풀 수 있는 문제이다. 

CompareTo 또는 Comparable 관련해서는 이전에 작성했던 글 참조하면 좋을 것 같다.

 

2022.02.20 - [프로그래밍공부(ProgrammingStudy)/자바(JAVA)] - (JAVA/자바)compareTo와 Comparator 그리고 정렬

(JAVA/자바)compareTo와 Comparator 그리고 정렬