백준 1927번: 최소 힙 with Java

최소 힙

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음) (하단 참고)

128 MB

107149

51866

40957

49.406%

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

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

입력

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

출력

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

예제 입력 1 복사

9
0
12345678
1
2
0
0
0
0
32

예제 출력 1 복사

0
1
2
12345678
0

 

 

---

 

 

우선순위 큐란 무엇인가... 부터 생각해보자 

우리가 아는 큐는?? FIFO 먼저 들어간 놈이 먼저 나간다 이거다...

근데 우선순위 큐는??? 우선순위가 높은 놈이 먼저 나간다 한 마디로 패스트트랙...

 

우선순위 큐는 힙을 사용해 구현한다.

* 최대 힙: 부모노드 >= 자식노드 

부모노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리

 

* 최소힙: 부모노드 <= 자식노드

부모노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리

 

내가 풀 거는 최소 힙이기 때문에...

이거 풀고 최대 힙도 풀 거긴 하지만 ㅎㅎ

 

 

자 일단 문제 조건 해석

자연수 입력 받으면 -> 큐에 추가

0 입력 받으면 가장 작은 수 뱉기... (sb에 추가해서 한 번에 출력하면 될 듯?)

비어있는데 뱉으라고 하면 0 출력

 

네 해보겠습니다~

 

열심히 구글링하다가(지피티 안 됨이슈;;;)  자바에 PriorityQueue라는 친구가 있다는 걸 알게 되었다. 자바 이 친구... 역시 좋은 걸

이 친구는 기본값이 최소란다. 그니까 내가 설정을 안 건드려도 된다는 말이다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
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<Integer> minQueue = new PriorityQueue<Integer>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            x = Integer.parseInt(br.readLine());
            
            if (x > 0) {
                minQueue.add(x);
                continue;
            }    // 자연수면 큐에 넣기
            
            if (minQueue.isEmpty()) {
                sb.append(0).append("/n");
                continue;
            }    // 0인데 비어있을 때 -> sb에 0 추가
            
            sb.append(minQueue.poll()).append("/n");    // 0이고 값 있을 때 최소값 빼내기
        }
        
        System.out.println(sb);
	}  
}

 

간단하게 짜버렸다. if-else가 별루 좋지 않다구 해서 if 문만 만들고 continue로 올려버리기로 했다.

과연 결과는?!!!!

 

 

...

왜 틀렸을까나

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
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<Integer> minQueue = new PriorityQueue<Integer>();    // 최소 힙
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            x = Integer.parseInt(br.readLine());
            
            if (x > 0) {
                minQueue.add(x);
                continue;
            }    // 자연수면 큐에 넣기
            
            if (minQueue.isEmpty()) {
                sb.append("0").append("/n");
                continue;
            }    // 0인데 비어있을 때 -> sb에 0 추가
            
            sb.append(minQueue.poll()).append("/n");    // 0이고 값 있을 때 최소값 빼내기
        }
        
        System.out.println(sb);
	}  
}

 

 

당연히 또 틀림

왜 안 되냐고!!!!! 지피티도 안 되는디

 

 

와 제정신이 아닌가보다 역슬래쉬 아니고 슬래쉬 썼다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
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<Integer> minQueue = new PriorityQueue<Integer>();    // 최소 힙
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            x = Integer.parseInt(br.readLine());
            
            if (x > 0) {
                minQueue.offer(x);
                continue;
            }    // 자연수면 큐에 넣기
            
            if (minQueue.isEmpty()) {
                sb.append(0).append("\n");
                continue;
            }    // 0인데 비어있을 때 -> sb에 0 추가
            
            sb.append(minQueue.poll()).append("\n");    // 0이고 값 있을 때 최소값 빼내기
        }
        
        System.out.println(sb);
	}  
}

 

 

 

 

네... 천하의 빡대가리짓... 암튼 맞았습니다 하하