[Python/BOJ] 25827. 시간 구간 다중 업데이트 다중 합

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

25827번: 시간 구간 다중 업데이트 다중 합

문제

시간 구간에 대한 질의를 처리하려고 한다. 전체 시간 구간은 [00:00:00,23:59:59]이다. h:m:s는 h시 m분 s초를 나타낸다. 전체 시간 구간은 길이가 1초인 구간으로 나누어져 있다. 즉, 전체 시간 구간은[00:00:00,00:00:01], [00:00:01,00:00:02], ..., [23:59:58,23:59:59]인 구간으로 나누어져 있다.

시간 구간에 대한 n개의 질의가 저장된 배열 A가 주어진다. 배열 A에 저장된 n개의 질의는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 1을 나타내고 두 번째가 유형 2를 나타낸다.

• 1 h1:m1:s1 h2:m2:s2 : 시간 구간 [h1:m1:s1,h2:m2:s2]에 1을 더한다.
• 2 h1:m1:s1 h2:m2:s2 : 시간 구간 [h1:m1:s1,h2:m2:s2]의 값을 출력한다.

시간 구간 [h1:m1:s1,h2:m2:s2]에 1을 더하는 유형 1의 질의는 시간 구간 [h1:m1:s1,h2:m2:s2]에 포함된 길이가 1초인 모든 구간에 1을 더하는 것을 의미한다. 예를 들어, [00:00:02,01:02:03]에 1을 더하는 질의는 [00:00:02,00:00:03], [00:00:03,00:00:04], ..., [01:02:02,01:02:03] 구간에 1을 더하는 것을 의미한다.

시간 구간 [h1:m1:s1,h2:m2:s2]의 값을 출력하는 유형 2의 질의는 시간 구간 [h1:m1:s1,h2:m2:s2]에 포함된 길이가 1초인 모든 구간의 합을 출력하는 것을 의미한다. 예를 들어, [00:00:02,01:02:03]의 값을 출력하는 질의는 [00:00:02,00:00:03], [00:00:03,00:00:04], ..., [01:02:02,01:02:03] 구간의 합을 출력하는 것을 의미한다.

전체 시간 구간 [00:00:00,23:59:59]의 초깃값은 0이다. 배열 A에 저장된 첫 번째 질의부터 n번째 질의까지 순서대로 처리하면서 유형 2의 결과를 출력하자. 단, 배열 A에는 모든 유형 1의 질의가 유형 2의 질의보다 앞부분에 저장되어 있다.

입력

첫 번째 줄에 n이 주어진다.

두 번째 줄부터 n개의 줄에 배열 A에 저장된 n개의 질의가 첫 번째 질의부터 n번째 질의까지 순서대로 주어진다. 한 줄에 한 개의 질의가 주어진다.

출력

첫 번째 줄부터 유형 2의 질의 결과를 순서대로 한 줄씩 출력한다.

풀이

Code

import sys
input = sys.stdin.readline

def solution(n) :
    # 1. 누적합 수행 함수 정의
    def run_prefix_sum() :
        prefix_sum[0] = change[0]
        # 1-1.
        for i in range(1, l+1) :
            # 점화식에 따라 처리
            prefix_sum[i] = prefix_sum[i-1] + change[i]
        # 1-2.
        for i in range(1, l+1) :
            # 누적합 계산 수행
            prefix_sum[i] += prefix_sum[i-1]

    # 2. 누적합, 변화값 리스트 생성
    l = 24 * 60 * 60
    prefix_sum, change = [0 for _ in range(l+1)], [0 for _ in range(l+1)]
    # 3.누적합 최초 실행 여부 변수 생성
    state = False
    # 4.
    for _ in range(n) :
        information = list(map(str, input().rstrip().split(' ')))
        # 4-1. 시간 구간을 초로 변환
        start, end = sum([x * s for x, s in zip(map(int, information[1].split(':')), [3600, 60, 1]) if x]), sum([x * s for x, s in zip(map(int, information[2].split(':')), [3600, 60, 1]) if x])
        # 4-2. 유형 1의 경우
        if information[0] == '1' :
            # 4-2-1. 변화값 입력
            change[start] += 1
            change[end] -= 1
        # 4-3. 유형 2의 경우
        else :
            # 4-3-1. 최초 누적합 실행
            if not state :
                state = True
                run_prefix_sum()
            # 4-3-2. 값 출력
            print(prefix_sum[end - 1] - prefix_sum[start - 1]) if start else print(prefix_sum[end - 1])
if __name__ == "__main__" :
    n = int(input())
    solution(n)