백준 28070 : 유니의 편지쓰기

구간합 문제
특정 구간에 대해 값을 더해야 되는 경우, 그리고 그러한 연산 횟수가 많은 경우 필요한 알고리즘이다.

최근에 본 H기업의 코딩테스트 마지막문제로 이 알고리즘을 사용해야되는 문제가 나왔다.

📜 문제 바로 가기 : 백준 유니의 편지쓰기

제출코드

import sys
input = sys.stdin.readline

def transferIdx(date): # 날짜 형식을 인덱스로 변환하는 함수
    year = int(date[:4])
    day = int(date[5:])
    return (year - 2000)*12 + (day-1)

def transferDate(idx): # 인덱스를 날짜로 변환하는 함수
    year = str(idx//12 + 2000)
    day = str(idx%12+1)
    if len(day) == 1:
        day = "0"+day
    return year+"-"+day

N = int(input())
prefix = [0] * ((9999 - 2000 + 1) * 12 + 1) # 문제에서 주어진 범위
for _ in range(N):
    start, end = input().split()
    startIdx = transferIdx(start)
    endIdx = transferIdx(end)
    prefix[startIdx] += 1
    prefix[endIdx+1] -= 1

for i in range(1, len(prefix)):
    prefix[i] += prefix[i-1]

maxValue = 0
maxIdx = -1
for i in range(len(prefix)):
    if prefix[i] > maxValue:
        maxValue = prefix[i]
        maxIdx = i

print(transferDate(maxIdx))

접근방법

해당 구간에 맞춰 시작점에 +1, 마지막점 이후에 -1 을 해준다.
그리고 이후에 누적합을 이용하면 해당구간만 +1 을 한 결과를 가질 수 있다.