문제 바로가기

나의 풀이

처음에는 이차원 배열인 map을 만들어 실제로 석순과 종유석이 존재하는 위치에는 1씩 더해줘서 그래프를 만들고, 각각의 행을 더한 값 중에서 최소값을 구하는 식으로 문제를 풀었지만 메모리 초과가 났다!

메모리 초과를 해결하기 위해서 h 길이를 가진 1차원 배열을 만들고, 석순은 끝에서부터, 종유석은 앞에서부터 1씩 더해줘서 메모리 문제를 해결하려 했다. 그러나 시간 초과가 났다!

고민하던 중, 누적합 알고리즘이 떠올랐고, 1차원 배열에 석순인 경우 어차피 마지막까지 더해줘야하므로 start 부분에 1만 더해주고, 종유석인 경우 start 부분에는 1을 더해주고 end + 1 부분에는 -1을 해줬다.

누적합으로 한번에 계산해주니 시간초과 문제도 해결할 수 있었다.

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

class Main {

    static int n, h;

    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());
        int[] sum = new int[h];

        for (int i = 0; i < n / 2; i++) {
            int length1 = Integer.parseInt(br.readLine());
            sum[h - length1] += 1;
            int length2 = Integer.parseInt(br.readLine());
            sum[0] += 1;
            sum[length2] -= 1;
        }

        for (int i = 0; i < sum.length - 1; i++) {
            sum[i + 1] += sum[i];
        }

        int min = 1000000;
        int count = 0;
        for (int i = 0; i < sum.length; i++) {
            if (min > sum[i]) {
                min = sum[i];
                count = 1;
            } else if (min == sum[i]) count++;
        }

        System.out.printf("%d %d", min, count);
    }
}