[백준/G5/구현/자바] 11509 풍선 맞추기

💡 문제

 

큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다.

진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다.

진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다.

화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다.

화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다.

화살은 계속해서 가던길을 가는데 높이는 1 줄어든다.

그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다.

 

⌨ 입력

 

첫째 줄 정수 N ( 1 <= N <= 100만 )

두번째 줄 N개 각 풍선의 높이 ( 1 <= H <= 100만 ) 

 

💻 출력 / 제한

 

필요한 최소한의 화살의 수를 출력 하시오.

 

---

 

풀이 방법

구현 문제 라고 생각 합니다.

 

int[ ] arr = { 2, 1, 5, 4, 3 } 인 배열을 만듭니다.

배열을 1번만 돌며 해당 풍선의 높이의 화살이 없으면 Map에 넣어줍니다.

 

Map < Integer, Integer >  

Key : 풍선의 높이  Value : 화살의 개수

 

제가 구현한 방법은 map에 풍선 높이의 화살이 없을 경우

해당 풍선의 높이를 쏘고 높이 - 1 한 값을 map에 넣는 것입니다.

 

 

만약에 해당 높이의 풍선을 쏠수 있는 화살이 있다면

해당 높이의 화살의 수 (Value) 를 가져와서 처리 합니다.

 

 

---

 

전체 코드

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class BalloonFit11509 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // arr 풍선의 높이 받기
        int[] arr = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // map -> (key : 풍선의 높이 , value : 쏠 수 있는 화살의 개수)
        Map<Integer, Integer> map = new HashMap<>();

        int arrow = 0;
        // arr 크기 만큼 반복
        for(int i = 0; i < N; i++){
            int heightArrow = arr[i];
            int nextHeightArrow = arr[i] - 1;

            // 해당 풍선을 쏠 수 있을 경우
            if(map.containsKey(heightArrow)){
                int heightArrowCount = map.get(heightArrow) - 1;

                if(heightArrowCount == 0) {
                    map.remove(heightArrow);
                }
                else map.put(heightArrow, heightArrowCount);

                boolean error = nextHeightArrow < 1;
                if(!error) map.put(nextHeightArrow, map.getOrDefault(nextHeightArrow, 0) + 1);
            }
            // 풍선을 쏠 수 없는 경우
            else{
                if(nextHeightArrow >= 1) map.put(nextHeightArrow, map.getOrDefault(nextHeightArrow, 0) + 1);
                arrow += 1;
            }
        }
        System.out.println(arrow);
    }
}

 

문제 Link : 11509번: 풍선 맞추기 (acmicpc.net)