백준 11509번: 풍선 맞추기 (Python/Java)

https://www.acmicpc.net/problem/11509

11509번: 풍선 맞추기

 

 

 

접근

---

이 문제의 키포인트는 현재 높이의 화살과 이 화살이 풍선을 만날 수 있도록 체크하는 방법이다. 이 부분만 구현한다면 문제는 굉장히 쉽다. 우선 문제 조건을 확인해보자. 문제 조건에서 높이는 1에서 1000000까지다. 우리는 배열을 통해서 높이에 있는 화살 개수를 체크할 것이다. 이 경우에는 설정을 어떻게 해야 할까? 높이를 인덱스 번호로 두고 해당 인덱스에 들어있는 값을 화살의 개수로 두면 될 것이다. 물론 배열의 인덱스는 0부터 시작하니 정확히 말하면 1000001까지의 배열을 만들어주자. 

 

이제 각 인덱스는 화살의 높이를 뜻한다. 이제 한번 화살을 쏴 해당 높이에 화살이 있는 경우, 해당 인덱스에 +1 해주도록 하자. 이제부터는 간단하다. 풍선이 놓여있는 순서대로 풍선 높이를 화살 개수 배열에 대입해본다. 해당 높이에 화살이 있다면 풍선이 터지고, 그렇게 되면 해당 높이 화살 갯수에 -1을 한번 해줘야 한다.. 이제 높이-1에 화살이 하나 생기니 높이-1 인덱스에 +1 해주면 된다. 만약에 풍선 높이에 화살이 없다면? 화살을 새로 쏴야 한다. 그렇단 얘기는 풍선 높이에 화살이 없을 때마다 최종 결괏값에 +1을 해준다는 뜻이다. 이 방법을 통해 풍선 배열 마지막까지 확인하고 최종 결괏값을 출력하면 된다.

 

 

 

풀이

---

Python

balloonNum = int(input())

subBalloon = list(map(int, (input()).split()))
balloonList = [0 for i in range(1000001)]

result = 0
for i in subBalloon:
    
    if balloonList[i] == 0:
        balloonList[i-1] += 1
        result += 1

    else:
        balloonList[i] -= 1
        balloonList[i-1] += 1
    
print(result)

 

 

Java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        int balloonNum = Integer.parseInt(scan.nextLine());

        String[] firstLine = (scan.nextLine()).split(" ");
        int[] subBalloon = new int[balloonNum];
        for (int i = 0; i < balloonNum; i++) {
            subBalloon[i] = Integer.parseInt(firstLine[i]);
        }
        int[] balloonList = new int[1000001];

        int result = 0;
        for (int i : subBalloon) {
            if (balloonList[i] == 0) {
                balloonList[i - 1]++;
                result++;

            } else {
                balloonList[i]--;
                balloonList[i - 1]++;
            }
        }

        System.out.println(result);

    }

}

 

 

 

후기

---

난이도는 골드 5로 평범했지만 구현 부분에 있어 상당히 애먹었던 문제. 높이나 순서를 인덱스 번호로 놓고 푸는 방법은 흔히, 또 자주 사용했던 방법이었는데 이 문제를 풀 때는 왜인지 그게 그렇게 생각이 안 났다. 

 

이 방법이 아니라 2중 for문을 이용해서 풀려고 했었는데 풀면서도 계속 '이거 무조건 시간 초과인데...' 하는 생각이 들었다. 아니나 다를까, 역시나 시간 초과. 단순히 조건만 놓고 보더라도 최대 범위를 넣으면 연산이 억대가 넘어가기 때문에 무조건 틀릴 수밖에 없는 방법이었다.

 

구현 방법에 있어 유연한 사고를 하는 것이 중요한 것 같다. 아직 그렇게까지 성장하지 못했나 하는 생각이 들어 조금 아쉬운 마음이 든다.