백준 28018 (시간이 겹칠까?) - java

문제

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

 

얼마 전 부산대학교 커뮤니티에 어느 시간대에 도서관의 열람실 좌석이 널널한지에 관한 질문 글이 올라왔다.

작성자는 지난주 일요일에 언제 도서관의 열람실을 이용했는지 댓글을 달아달라고 부탁하였다.

이에 많은 학생이 본인이 있던 시간을 댓글로 달아주었다.

자랑스러운 부산대학교 학생들은 공부하는 시간에는 도서관에 배정된 자신의 좌석을 비우지 않는다.

각 좌석은 사용이 종료되는 시각에 곧바로 선택될 수 없다.

편의상 시각은 0부터 1_000_000까지 주어지며 정수 단위로 구분된다. 특정한 시각에 선택할 수 없는 좌석이 몇 개였는지 알아보자.

 

유형 : 누적합(imos)

 

접근 방식

• 입력의 크기가 1_000_000이기 때문에 일반적인 방식으로는 시간 초과가 날듯하다.
• imos를 통해 O(N)으로 해결하는 법이 좋다!

 

전체 코드

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

public class Main {

    static int n,q;
    static int[] time;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());

        time = new int[1_000_002];

        for(int i = 1 ; i <= n ; i++) {
            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 <= 1_000_000 ; i++) {
            time[i] += time[i - 1];
        }

        st = new StringTokenizer(br.readLine()," ");
        q = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= q ; i++) {
            int qq = Integer.parseInt(st.nextToken());

            sb.append(time[qq]+"\n");
        }

        System.out.print(sb);
        br.close();
    }
}