[백준] 3020: 개똥벌레 - JAVA

in Algorithm on 기타

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

풀이

석순과 종유석이 번갈아 나오는 동굴을 장애물을 파괴하면서 지나가야한다.

높이별로 만나는 장애물의 개수를 세어 최솟값을 찾는 문제이다.

처음에 누적합으로 문제를 풀었고, 이분 탐색으로 푸는 방법이 있다고하여 찾아보았다.

  • 이분 탐색

    이분 탐색으로 풀기 위해서는 석순과 종유석을 따로 배열에 담아준다.

    bottom배열에 석순을, top배열에 종유석을 담았다.

    이분탐색을 위해 배열을 정렬한 뒤 1부터 H까지 높이을 key로 하여 이분탐색을 진행한다.

    석순과 종유석을 각각 진행하여 해당 key값(key값보다 크거나 같은 첫번째 인덱스)을 찾아 arr.length - rigth을 반환하면 해당 구간의 장애물의 개수를 구할 수 있다.

  • 누적 합

    누적 합으로 풀기 위해 우선 높이를 length로 하는 배열을 만들고 입력받으면서 [석순의 높이]를 인덱스로 하는 값을 증가시키고,

    종유석의 경우 [높이 - 종유석의 높이]의 값을 감소, [높이]의 값을 증가시킨다.

    입력 후 H부터 하향식 탐색하며 arr[i] += arr[i + 1]하여 누적 합해준다.

    누적 합이 된 배열을 탐색하여 최솟값을 찾는다.

이분 탐색

메모리: 34068KB

시간: 616ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

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());

        int[] bottom = new int[N / 2];
        int[] top = new int[N / 2];
        for (int i = 0; i < N / 2; i++) {
            bottom[i] = Integer.parseInt(br.readLine());
            top[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(bottom);
        Arrays.sort(top);

        int min = Integer.MAX_VALUE;
        int cnt = 0;
        for (int i = 1; i < H + 1; i++) {
            int tmp = binarySearch(0, N / 2, i, bottom) + binarySearch(0, N / 2, H - i + 1, top);

            if (tmp < min) {
                min = tmp;
                cnt = 1;
            } else if (tmp == min) {
                cnt++;
            }
        }

        System.out.println(min + " " + cnt);
    }

    private static int binarySearch(int left, int right, int key, int[] arr) {
        while (left < right) {
            int mid = (left + right) / 2;

            if (arr[mid] >= key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return arr.length - right;
    }

}

누적 합

메모리: 29272KB

시간: 320ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

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());

        int[] arr = new int[H + 1];
        for (int i = 0; i < N; i++) {
            int a = Integer.parseInt(br.readLine());
            if (i % 2 == 0) {
                arr[a]++;
            } else {
                arr[H - a]--;
                arr[H]++;
            }
        }

        for (int i = H - 1; i > 0; i--) {
            arr[i] += arr[i + 1];
        }

        int min = Integer.MAX_VALUE;
        int cnt = 0;
        for (int i = 1; i < H + 1; i++) {
            if (arr[i] < min) {
                min = arr[i];
                cnt = 1;
            } else if (arr[i] == min) {
                cnt++;
            }
        }

        System.out.println(min + " " + cnt);
    }

}