[Python/파이썬] 백준 20440번 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

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

 

문제

🎵니가 싫어 싫어 너무 싫어 싫어 오지마 내게 찝쩍대지마🎵 - 유자, 모기송 中

모기를 싫어하는 지동이는 어느 날 문득 자신의 방에 모기가 가장 많이 있는 시간대가 언제인지 궁금해졌다. 다행히 지동이 방은 최첨단 시스템이 갖춰져 있어 어떤 모기가 방에 언제 입장했고 언제 퇴장했는지를 기록할 수 있다.

지동이를 도와 모기들의 방 입장, 퇴장 시각이 주어졌을 때 모기들이 가장 많이 있는 시간대와 해당 시간대에 모기가 몇 마리가 있는지 구하는 프로그램을 만들어보자. 

입력

첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ $N$ ≤ 1,000,000)가 주어진다.

다음 $N$개의 줄에 모기의 입장 시각 $T_E$과 퇴장 시각 $T_X$이 주어진다. (0 ≤ $T_E$ < $T_X$ ≤ 2,100,000,000)

모기는 [$T_E$, $T_X$)동안 존재한다.

출력

첫째 줄에 지동이 방에 모기가 가장 많이 있는 시간대의 모기 마릿수를 출력한다.

지동이 방에 모기가 가장 많이 있는 시간대의 연속 구간 전체를 [$T_{Em}$, $T_{Xm}$)이라고 할 때,

둘째 줄에 $T_{Em}$, $T_{Xm}$을 공백으로 구분하여 출력한다. 단, 여러 가지 방법이 있으면 가장 빠른 시작 시각을 기준으로 출력한다.

코드

import sys
input = sys.stdin.readline
from collections import defaultdict

n = int(input())
mosquito = defaultdict(int) # key:시각, value:모기 수
for _ in range(n):
    e, x = map(int, input().split())    # 모기 입장/퇴장 시각 
    mosquito[e] += 1
    mosquito[x] -= 1

acc = [0]
max_mos = 0
start, end = 0, 0
flag = False
key_lst = sorted(mosquito.keys())
for i in range(len(key_lst)):
    acc.append(acc[i]+mosquito[key_lst[i]])
    if max_mos < acc[i+1]:  # 최대 모기 구간 시작
        max_mos = acc[i+1]
        start = key_lst[i]
        flag = True
    if flag and acc[i+1] < max_mos: # 최대 모기 구간 끝남
        end = key_lst[i]
        flag = False

print(max_mos)
print(start, end)

 

시간의 범위가 0 ≤ $T_E$ < $T_X$ ≤ 2,100,000,000으로 매우 크기 때문에 배열을 사용했다가는 메모리 초과가 날 것이다. 그래서 시각을 key값, 모기 수를 value값으로 갖는 defaultdict(mosquito)를 사용하였다.

모기가 입장하는 시각(e)에는 value값을 +1, 퇴장하는 시각(x)에는 -1을 하고 키값을 오름차순 정렬(key_lst)하여 value값들의 누적합(acc)을 구해주면 시각별로 방에 있는 모기의 수를 구할 수 있다.