JAVA_절댓값 힙 구하는 알고리즘 (Priority Queue Algorithm)

자바 알고리즘-  절댓값 구하는 알고리즘

시간 제한	메모리 제한
2 초	256 MB

 

Priority Queue Algorithm 설명

문제

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

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

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

입력

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

출력

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

▶ 나의 문제풀이 

우선 이 문제의 핵심은 입력 받는 값이 절댓값으로 비교 시 -1과 1이 같을 때에는 작은 수가 먼저 정렬이 되어야 하고

입력받는 값이 0으로 입력이 될 때, 큐에 아무것도 없으면 0을 리턴

값이 있으면 root의 값을 꺼내줍니다.

힙정렬 by jju_developer

여기서 핵심은 0이 들어와 루트를 빼낼 때, 

위에 있는 값을 빼면 자식노드만 있는 이상한 모양이 되니까

가장 마지막에 있는 값과 교체를 해준 후, 문제 풀이를 하였습니다.

 

▶ 나의 코드 

package algorithm.doit;

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

public class 절댓값힙구하기 {

		public static void main(String [] args) throws IOException {

			// 맨처음 콘솔창에 입력되는 값은 연산의 개수로 설정
			System.out.println("연산의 개수를 입력하세요");
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			
				int n = Integer.parseInt(br.readLine());
				// 우선순위 큐를 선언해주고 타입은 Integer로 해준다.
				//	자바의 우선순위 큐는 힙메모리를 사용하며, 이진트리 구조이다. 
				
//				그리고 최소힙을 구현하므로, 작은값이 큐의 뿌리가 된다.......
				
				PriorityQueue<Integer>myQueue = new PriorityQueue<>((x1,x2)->{
//					여기서 PriorityQueue 객체를 선언하고 타입을 Integer로 받는다 선언한뒤
//					매개변수 두개를 받는다
					
				//문제에서 -231부터 231범위내의 값을 받는다고 하였으므로
//					각 매개변수들을 int형으로 언박싱해준다.
//				오토 언박싱은 -128부터 128까지만 진행되므로!
					
					//절댓값 비교할 변수 저
					int first = Math.abs(x1);
					int second = Math.abs(x2);
					
					// 우선순위 큐 클래스 안에 comparator라는 메소드를 가지고 있고
//					comparator 클래스 안의 compare 메소드를 오버라이딩 했으므로
//					람다식으로 매개변수를 바꿔준것이다.
					
					 if(first == second)
//						 여기서 x1>x2면 양수값 1을 반환하므로 우선순위가 밀린다.
//						 따라서 절대값이 같은경우엔 음수가 더 앞에 정렬되고
						 return x1>x2? 1:-1;
					 else
//				 절대값이 다르면 대소관계대로 정렬
//				 만약 첫번째값 - 두번째 값이 >0 이면 첫번째 값이 더 큰값이므로 (7-5)= 2 >0
//				 두번째값을 먼저 큐에 넣어주고, 그다음 첫번째값을 넣어준다.
//		       만약 첫번째값 - 두번째값이 <0 이면 두번째 값이 더 큰값이므로 (5-7)= -2 < 0
//				 첫번째값을 큐에 먼저 넣어주고, 그다음 두번째값을 넣어준다.	
		 				 return first - second;
				});
				
				for(int i = 0; i<n; i++) {
//					연산의 개수만큼 for를 돌립니다. n개의 수를 받을 것 입니다.
//					입력받은 값을 int로 변환해 input에 담아준다.
					int input = Integer.parseInt(br.readLine());
					
					// 입력받은 값이 0일때, 우선순위 큐 안의 값을 출력해줘야 하므로
					if(input==0) {
						if(myQueue.isEmpty()) 
							System.out.println("0");
						//0을 입력 받았는데 큐가 비어있으면 0을 리턴
						else
							// 아니라면 정렬되어있는 큐의 첫번째 값을 출력하고 삭제하는
							// poll 메소드를 사용한다.
							System.out.println(myQueue.poll());
					}
					// 0이 아니라면 큐에 입력받은 값을 집어넣는다.
					else {
						myQueue.add(input);
					}
				}
			}

		}

 

 

 

 

 

<참고>

책: do it 알고리즘 코딩 테스트 자바 편

코딩 테스트: https://www.acmicpc.net/

Baekjoon Online Judge

Priority Queue Algorithm 설명