[백준/Java] 28018 시간이 겹칠까?

문제

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

풀이방법

그냥 배열 돌려가면서 다 더해주기했는데 시간 초과남

time[S] += 1 time[E+1] -=1

time 배열에 대한 누적합 적용 --> 각 시각에 사용중인 좌석

time[1] += 1 time[6] += -1

time[3] += 1 time[7] += -1

차분배열

시간: 0 1 2 3 4 5 6 7

변화량: 0 1 0 1 0 0 -1 -1

누적합좌석 수: 0 1 1 2 2 2 1 0

풀이

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));
        int N = Integer.parseInt(br.readLine());
        int[] time = new int[1000002];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());

            time[S] += 1;
            time[E + 1] -= 1;
        }

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

        int Q = Integer.parseInt(br.readLine());
        StringTokenizer querySt = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i<Q; i++) {
            int t = Integer.parseInt(querySt.nextToken());
            sb.append(time[t]).append('\n');
        }
        System.out.println(sb);
    }
}