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

문제

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

시간 복잡도

• n만큼의 반복 + 최대 n만큼의 탐색 + 최대 n크기로 정렬 -> $O(n)$

문제 접근법

• 접근 방법이 안떠올라서 구글링 -> 참조1, 참조2

1. 딕셔너리에 모기의 입퇴장 시간을 기록한다. -> 입장 시간: +1, 퇴장 시간: -1
2. 가장 많은 시간의 모기 수, 현재의 모기 수, 답이 될 입퇴장 시간을 초기화한다.
3. 정확한 정답을 위한 flag를 초기화한다. -> flag가 없는 경우, 퇴장 시간이 뒤로 밀릴 수 있다.
   (최대치로 증가했다 감소하는 패턴이 반복되면, 퇴장시간이 마지막 패턴의 감소하는 시간이 될 수 있기 때문)
4. 딕셔너리를정렬하여 가장 처음부터 탐색한다.
   4-1. 현재 모기 수에 현재 키에 해당하는 값(현재 시간의 모기 수)을 더한다.
   4-2. 현재 모기 수가 가장 많은 시간의 모기 수보다 크다면 갱신을 해준 후, 입장 시간을 현재 시간으로 설정하고 flag를 True로 체크해준다.
   4-3. 현재 모기 수가 가장 많은 시간의 모기 수보다 작으면서 flag가 True면, 퇴장 시간을 현재 시간으로 설정하고 flag를 False로 체크해준다.

정리

• 모기의 정보가 들어있는 시간만을 차례대로 탐색하면서, 모기의 수가 최대가 되는 시간을 입장 시간으로 갱신하고 최대치에서 감소하는 시간을 퇴장 시간으로 갱신한다.
• 같은 패턴이 여러 번 반복되어도 가장 빠른 시간대의 구간만을 출력해야 하기 때문에 flag가 필요하다.

코드

# BOJ
# G3 - 20440(🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1)

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

n = int(input())
d = defaultdict(int)

for _ in range(n):
    s, e = map(int, input().split())
    d[s] += 1
    d[e] -= 1

max_mos, now_mos = 0, 0
tem, txm = 0, 0
flag = False

for i in sorted(d.keys()):
    now_mos += d[i]
    if now_mos > max_mos:
        max_mos = now_mos
        tem = i
        flag = True
    elif now_mos < max_mos and flag:
        txm = i
        flag = False

print(max_mos)
print(tem, txm)