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

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

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:08:55

 

---

 

문제 설명

 

 

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

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

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

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

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

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

 

 

입력 및 출력

 

입력

 

댓글을 달아준 학생 수 N이 주어진다. (1 <= N <= 100,000)

다음 $N$개 줄에는 각 학생의 좌석 배정 시각 S와 종료 시각 E가 주어진다. (1 <= S <= E <= 1,000,000)

다음 줄에는 특정한 시각의 개수 Q가 주어진다. (1 <= Q <= 100,000)

다음 줄에는 알고자 하는 특정 시각 Q개가 주어진다.

 

출력

 

특정 시각에 선택할 수 없는 좌석 수를 주어진 순서에 따라 줄마다 출력하라.

 

입력 예시

 

1
1 3
2
2 4

 

출력 예시

 

1
0

 

 

---

 

풀이

 

코테 재활치료 3일차. 누적합 문제로 몸풀기에 들어가보자.

 

전체 시간 구간을 T라고 두자. 일일히 구간을 업데이트하는 경우는 매우 비효율적이다. 따라서 한번에 증가 시점, 감소 시점을 누적합으로 구한 후 업데이트함으로써 O(N + T) 시간복잡도로 모든 구간에 대한 좌석 여부를 구할 수 있다.

 

 

풀이 코드 (Python)

import sys

input = sys.stdin.readline
MAX = 10**6 + 1

student_map = [0] * (MAX + 1)


def map_student():
  for _ in range(int(input())):
    start, end = map(int, input().split())
    student_map[start] += 1
    student_map[end+1] -= 1
  for i in range(1, MAX + 1):
    student_map[i] += student_map[i - 1]


def query():
  Q = int(input())
  for q in map(int, input().split()):
    print(student_map[q])


if __name__ == "__main__":
  map_student()
  query()

 

 

풀이 코드 (Go)

package main

import (
	"bufio"
	"fmt"
	"os"
)

const MAX = 1000001

var studentMap = [MAX + 1]int{}
var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func mapStudent() {
	var n, start, end int
	fmt.Fscanln(reader, &n)
	for i := 0; i < n; i++ {
		fmt.Fscanln(reader, &start, &end)
		studentMap[start] += 1
		studentMap[end+1] -= 1
	}
	for i := 1; i <= MAX; i++ {
		studentMap[i] += studentMap[i-1]
	}
}

func query() {
	var q, query int
	fmt.Fscanln(reader, &q)
	for i := 0; i < q; i++ {
		fmt.Fscan(reader, &query)
		fmt.Fprintln(writer, studentMap[query])
	}
}

func main() {
	defer writer.Flush()
	mapStudent()
	query()
}

 

 

p.s. golang의 기본 입출력 함수는 생각보다 오버헤드가 크다... 이걸로 좀 해멨다.

풀이 완료!