[코드트리] 블럭쌓는 명령 - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/block-stacking-commands?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

1번 칸부터 N번째 칸까지 총 N개의 칸이 있습니다. 이 중 Ai에서 Bi까지 각각 블록을 1씩 쌓으라는 명령이 K번 주어집니다. 1번 칸부터 N번 칸까지 쌓인 블록의 개수를 오름차순으로 정렬했을 때, 그중 가운데 숫자를 출력하는 프로그램을 작성해 보세요.

단, N은 항상 홀수로 주어집니다.

 

입력 예시

7 4
5 5
2 4
4 6
3 5

 

출력 예시

1

 

 

코드

첫 번째 줄에 n과 k가 공백으로 구분되어 주어지고, 두 번째 줄부터 k개의 줄에 걸쳐 a와 b가 공백으로 구분되어 주어진다.

• 1 <= n <= 1,000,000
• 1 <= k <= 25,000
• 1 <= a, b <= n

반복문으로 풀면 시간 초과가 발생한다. 누적 합을 통해 O(1)의 시간 복잡도로 빠르게 처리할 수 있는 문제다.

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        // 블록을 쌓을 배열
        int[] arr = new int[n + 2]; // n + 2 (b == n인 경우를 방지하기 위함)
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // arr[a]는 증가, arr[b + 1]은 감소
            arr[a]++;
            arr[b + 1]--;
        }
        br.close();

        // 누적합을 완성된 블록 배열 만들기
        for (int i = 1; i <= n + 1; i++) {
            arr[i] += arr[i-1];
        }

        // 오름차순 정렬
        Arrays.sort(arr);

        // 배열의 여분을 제외한 중간 인덱스의 값
        bw.write(String.valueOf(arr[arr.length / 2 + 1]));
        bw.flush();
        bw.close();
    }
}