[백준] 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

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

20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

누적 합을 활용하여 해결할 수 있는 문제입니다. 모기가 입장하는 시간에 +1, 퇴장하는 시간에 -1을 더해주고 순차적으로 더해나가면서 모기의 수가 가장 많이 등장하는 시간 구간을 기록해두면 됩니다. 처음에 시간을 기록하는 자료구조를 배열로 생각했었는데 시간이 21억이 넘어가기 때문에 O(N)에 배열을 탐색하는 것이 불가능하여 dict를 활용하여 시간을 기록하였습니다. 

 

import sys
from collections import defaultdict

# sys.stdin = open("input.txt", "r")

input = sys.stdin.readline

n = int(input())

time = defaultdict(int)

for _ in range(n):
    start, end = tuple(map(int, input().split()))
    time[start] += 1
    time[end] -= 1
ans = 0
cnt = 0
ans_start = 0
ans_end = 0
isUpdated = False

for t in sorted(time.keys()):
    # 값이 갱신되는 순간에 시작 시간을 저장해둔다.
    if cnt + time[t] > ans:
        ans_start = t
        ans = cnt + time[t]
        isUpdated = True

    # 답이 갱신된 적이 있고 값이 더 적어진다면 최장 기간이 끝난 것이므로 기록해준다.
    if isUpdated and cnt + time[t] < ans:
        ans_end = t
        isUpdated = False

    cnt += time[t]

print(ans)
print(ans_start, ans_end)