[백준 11509번] 풍선 맞추기 - java

문제 설명

1. 풍선의 수 N이 주어진다.

2. 왼쪽에서 오른쪽으로 화살을 쏘고, 풍선을 맞추게 되면 높이가 1줄어서 화살이 날아가게 된다.

3. 아래높이의 풍선이 있으면 또 이걸 터트리고 높이가 1 줄어든다.

4. 최소의 화살개수를 구하면 된다.

 

풀이 과정

 1. 그리디...겠지? 나는 걍 해쉬맵으로 구현했다.

 2. 풀이 과정은 이렇게 했다.

---

A. 풍선을 처음부터 순서대로 확인하면서, HashMap에 해당 높이에 있는 화살이 있는지 먼저 파악해준다.

B. 해당 높이에 화살이 없으면 쏴야하는 화살의 개수는 하나 늘고, 만약에 있으면 해당 높이의 화살을 하나 없애준다.

C. 어쨌든 이 화살은 풍선을 맞추었으니, 아래 높이의 화살로 변경될것이다.

D. 참고로, HashMap은 처음 풍선들의 위치를 받을때마다 0개로 초기화시켜 주었다. 그래야 구하기 편해서

---

 3. 쉽게 구하기는 했지만, 아마 시간복잡도에서 별로 좋은 방법이 아닐 것 같다는 생각이 든다. 개인적으로 이게 그리디인지 해쉬맵을 사용한 깡구현인지 모르겠다...

코드