[백준] 3020 - 개똥벌레(Java)

문제 파악

풀이

요약하자면 높이 [0, 1, ... h-1] 지점에 장애물이 몇개 있는지 판별하여, 장애물의 최솟값과 최솟값을 가지는 지점 수를 리턴하는 문제이다

 

예를 들어 석순 크기 3짜리가 높이 7인 동굴에 배치되어 있다면 구간 (0,1,2) 에 장애물이 하나씩 생긴다
이 때 (0,1,2) 구간마다 장애물의 카운터를 하나씩 늘려 주게 된다면 최악의 경우 복잡도는 O(H*N), 10^11가 될 것이다 🥲

 

위 방법 대신 장애물이 [0,h-1] 구간에 끊김 없이 배치되어 있기 때문에
장애물의 시작, 종점+1에 각각 증감인 +1, -1만 기록해주자
그 후 높이 H에 대해 누적합을 계산하면 복잡도가 O(H)로 줄게 된다.

구현 순서는 다음과 같다

증감을 기록할 일차원 배열(collision: int[N])을 사용하도록 한다.
주어진 장애물을 순회하며 종유석-석순에 따라 장애물의 시작(start) / 끝(end)을 통일해주고
start의 인덱스에는 +1을 기록, end+1의 인덱스에는 -1을 더해준다

collision의 기록이 끝났으면, 다시 [0, h-1] 범위에 대해 누적합을 계산하며, 최소값 및 구간 개수를 찾아주면 끝!

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        boolean isLow = true;
        int[] collision = new int[h];
        for (int i = 0; i < n; i++) {
            int len = Integer.parseInt(br.readLine());
            int start = isLow ? 0 : h - len;
            int end = isLow ? len : h;
            collision[start]++;
            if (end < h) {
                collision[end]--;
            }
            isLow = !isLow;
        }
        
        int accCollision = 0; // 누적합
        int minCollision = Integer.MAX_VALUE;
        int minCollisionCount = 0;
        for (int i = 0; i < h; i++) {
            accCollision += collision[i];
            if (accCollision < minCollision) {
                minCollision = accCollision;
                minCollisionCount = 1;
            } else if (accCollision == minCollision) {
                minCollisionCount++;
            }
        }
        System.out.println(minCollision + " " + minCollisionCount);
    }
}