[Java] 백준 11509번 풍선 맞추기

그리디 문제입니다.

최소의 화살을 사용해서 풍선을 터트려야 합니다.
풍선의 높이가 주어지고 화살은 직선으로 이동합니다.
화살이 풍선과 닿으면 풍선은 터지고 화살의 높이가 한칸 내려갑니다.

1_000_002 크기의 배열을 만들었습니다.
풍선의 높이가 입력으로 들어오면 해당 높이 + 1에 풍선이 있는지 확인합니다.
- 있으면 해당 높이에 -1을 하고 현재위치에 +1을 합니다.
- 없으면 현재위치에 +1을 합니다.

모든 풍선에 위의 과정을 반복해주고 배열안에 값들의 합을 출력해주었습니다.

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = null;

    int result = 0;
    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[1000002];

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; ++i) {
      int num = Integer.parseInt(st.nextToken());
      if (arr[num + 1] > 0) {
        --arr[num + 1];
      }
      ++arr[num];
    }

    for (int i = 0; i < arr.length; ++i) {
      result = arr[i] > 0 ? result + arr[i] : result;
    }

    bw.write(result + "\n");
    bw.close();
  }
}