[백준] 11509 풍선 맞추기 (Java)

[11509 풍선 맞추기]

난이도: 골드5

11509번: 풍선 맞추기

문제

 

입력

출력

---

[아이디어]

처음에는 남아있는 풍선 중 가장 높이 있는 풍선의 높이를 찾아주기 위해 풍선들을 모두 탐색하려고 하였다. 하지만 풍선의 개수가 100만개이므로 모든 풍선이 다 터질 때까지 계속 반복하면 시간초과가 난다. 따라서 풍선 중 가장 높이 있는 높이를 구해주기 위해 우선순위 큐를 사용하였다.

---

[JAVA 코드]

import java.io.*;
import java.util.*;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	static int N, result;
	static int [] balloon;
	static boolean [] visited;
	static PriorityQueue<Balloon> pQ = new PriorityQueue<>();
	
	static class Balloon implements Comparable<Balloon> {
		int height, idx;
		
		public Balloon(int h, int i) {
			this.height = h;
			this.idx = i;
		}

		@Override
		public int compareTo(Balloon o) {
			return Integer.compare(this.height, o.height) * -1;
		}
	}

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());

		balloon = new int [N];
		tokens = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			balloon[i] = Integer.parseInt(tokens.nextToken());
			pQ.offer(new Balloon(balloon[i], i));
		}

		visited = new boolean [N];
		int cnt = 0; // 터진 풍선 개수
		while(!pQ.isEmpty()) {
			int h = pQ.peek().height;
			int idx = pQ.poll().idx;
			
			if(visited[idx]) continue;
			result++;
			
			for(int i = idx; i < N; i++) {
				if(balloon[i] == h && !visited[i]) {
					h--;
					cnt++;
					visited[i] = true;
				}
				if(h == 0) break;
			}
			
			// 풍선 다 터뜨린 경우
			if(cnt == N) break;
		}
		
		System.out.println(result);
	}

}