백준 11509번 - 풍선 맞추기

문제

백준 11509번 - 풍선 맞추기

---

아이디어

N의 범위를 고려했을 때 최대한 O(N)안에 해결하도록 해야한다. 앞에서부터 새로운 화살이 필요한 경우만 카운팅 하도록 한다.

1. 입력

int[] arr = new int[n];
int[] arrows = new int[1_000_001];

StringTokenizer st = new StringTokenizer(br.readLine());

for (int i = 0; i < n; i++) {
    arr[i] = Integer.parseInt(st.nextToken());
}

• arrows 배열은 화살이 있는 높이에 대한 배열이다.

2. 정답 도출 후 출력

int ans = 0;

for (int i = 0; i < n; i++) {

    //새로운 화살을 쓰지 않아도 되는 경우
    if (arrows[arr[i]] > 0) {
        arrows[arr[i]]--;
    }
    //새로운 화살을 써야 하는 경우
    else {
        ans++;
    }
    
    //현재 높이에서 풍선을 터트리고 새로운 화살이 필요 없을 때까지 이동
    while (i < n - 1 && arr[i] - 1 == arr[i + 1]) {
        i++;
    }
    
    //최대한 긴 범위의 풍선들을 터트리고 나서 화살이 위치할 높이
    arrows[arr[i] - 1]++;
}

System.out.println(ans);

---

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

---

코드 구현 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_11509 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        int[] arrows = new int[1_000_001];

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

        int ans = 0;

        for (int i = 0; i < n; i++) {

            //새로운 화살을 쓰지 않아도 되는 경우
            if (arrows[arr[i]] > 0) {
                arrows[arr[i]]--;
            }
            //새로운 화살을 써야 하는 경우
            else {
                ans++;
            }

            //현재 높이에서 풍선을 터트리고 새로운 화살이 필요 없을 때까지 이동
            while (i < n - 1 && arr[i] - 1 == arr[i + 1]) {
                i++;
            }

            //최대한 긴 범위의 풍선들을 터트리고 나서 화살이 위치할 높이
            arrows[arr[i] - 1]++;
        }

        System.out.println(ans);
    }
}

코드 구현 - 파이썬

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
arrows = [0] * 1_000_001

ans = 0
i = 0
while i < n:
    if arrows[arr[i]] > 0:
        arrows[arr[i]] -= 1
    else:
        ans += 1

    while i < n - 1 and arr[i] - 1 == arr[i + 1]:
        i += 1

    arrows[arr[i] - 1] += 1
    i += 1

print(ans)