[백준 Java] 3020번 개똥벌레

💡문제

[Gold V] 개똥벌레 - 3020

문제 링크

성능 요약

메모리: 29804 KB, 시간: 252 ms

---

🤔접근법

범위 체크 및 시간복잡도 예상

• 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000
• $O(\sqrt {NH}$ 또는 $O(N)$ 이하 이어야 한다.

풀이법

❌ 접근 방법. 완탐

1. H개의 높이에 대해서 N개의 장애물에 대해 탐색하며 몇개의 장애물을 통과해야할지 판별→ $O(NH)$

➡️ 해당 풀이법의 시간 복잡도 : $O(NH)$

당연히 시간복잡도 초과

❌ 접근 방법. 완탐

1. 높이 H를 인덱스로 가지는 배열을 생성

2. 장애물을 차례대로 탐색하며 높이에 장애물이 존재하는 높이에 업데이트 → $O(NH)$

   길이가 2인 석순이라면 높이 1에 +1, 높이 2에 +1

   길이가 3인 종유석이라면 높이 3, 4,5를 +1

➡️ 해당 풀이법의 시간 복잡도 : $O(NH)$

시간복잡도 초과

**⭕ 접근 방법. imos (참고 블로그)

높이 H를 인덱스로 가지는 배열을 생성하고 장애물을 있는 부분을 1로 표현해보면 아래와 같다.

높이	1	2	3	4	5	6	7
	1
			1	1	1	1	1
	1	1	1
					1	1	1
	1	1	1	1	1
							1
합계	3	2	3	2	3	2	3

각 열의 합계를 구하면 각 높이에 해당하는 장애물의 개수가 된다.

그럼 위의 표를 간단하게 표현해보자. 장애물의 모든 높이를 1로 표현하지말고 장애물의 시작점을 +1로 표시하고 장애물이 끝나는 높이의 다음 위치를 -1로 표시하자.

높이	1	2	3	4	5	6	7
	+1	-1
			+1	-	-	-	-	-1
	+1	-	-	-1
					+1	-	-	-1
	+1	-	-	-	-	-1
							+1	-1
합계	3	-1	1	-1	1	-1	1	-3

위에서 구한 합계 배열을 누적합으로 만들어보자.

높이	1	2	3	4	5	6	7	8
합계의 누적합	3	2	3	2	3	2	3	0

처음에 구했던 장애물의 개수와 동일함을 알 수 있다.

1. 높이 H를 인덱스로 가지는 배열을 생성
2. 장애물이 시작하는 높이에 +1, 장애물이 끝나는 높이 다음 위치에 -1 로 기록한다. → $O(N)$
3. 배열을 누적합 배열로 바꾼다. → $O(H)$

➡️ 해당 풀이법의 시간 복잡도 : $O(max(N, H))$

---

😎SUCCESS

고냥 담박에 성공!

---

👩‍💻 코드

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

public class Main_3020 {
    static int N;           // 장애물 개수
    static int H;           // 터널 높이
    static int hurdle[];    // 각 높이에 대한 석순과 종유석의 개수를 저장하는 배열
    static int hurdleSum[]; // 각 높이까지의 누적합을 저장하는 배열
    static int min = Integer.MAX_VALUE; // 최소 파괴해야 하는 장애물 개수
    static int cnt;         // 최소 파괴하는 장애물 개수를 가지는 높이의 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());

        hurdle = new int[H];

        // 석순과 종유석의 개수 계산
        for (int i = 1; i <= N; i++) {
            int h = Integer.parseInt(br.readLine());
            if (i % 2 == 1) { // i가 홀수면 석순
                hurdle[0] += 1;
                hurdle[h] -= 1;
            } else { // i가 짝수면 종유석
                hurdle[H - h] += 1;
                // 끝점은 누적합 하면 0이라 기록할 필요 X
            }
        }

        hurdleSum = new int[H];
        hurdleSum[0] = hurdle[0];

        // 누적합 계산과 최소 파괴해야 하는 장애물 개수 갱신
        for (int i = 1; i < H; i++) {
            hurdleSum[i] = hurdleSum[i - 1] + hurdle[i];
            min = Math.min(min, hurdleSum[i]);
        }

        // 최소 파괴하는 장애물 개수를 가지는 높이의 개수 계산
        for (int i = 0; i < H; i++) {
            if (min == hurdleSum[i]) {
                cnt++;
            }
        }

        // 결과 출력
        System.out.println(min + " " + cnt);
    }
}