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

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

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

 

문제 이름만큼이나 짜증 났던 문제다.

 

문제 이름과 다르게 문제의 요구사항은 단순했다. N마리의 모기가 방에 들어온 시각과 나간 시각이 각각 입력으로 주어지고 방에 모기가 가장 많이 있었던 시간과 그때 모기의 수를 구하는 문제다.

 

O(N^2)의 시간의 풀이방법밖에 생각나지 않아서 답안을 참고하고 다시 풀어보니 아이디어만 알면 쉽게 풀 수 있는 문제였다.

 

이 문제는 모기의 입장 및 퇴장 시각만을 사용해서 풀 수 있다. 처음엔 리스트를 만들어서 모기가 머물렀던 구간(시간)에 해당하는 인덱스의 원소 값을 증가시켜 가장 많은 모기가 머물렀던 시간대를 찾으려고 했으나, 모기가 머물 수 있는 최대 시각이 21억이기 때문에 최대 21억 개의 원소를 가진 리스트를 만들어야 해서 불가능했다.

 

따라서 리스트가 아닌 사전을 이용한다. collection 라이브러리의 defaultdict는 Key-Value에서 값의 타입을 정해주면 키에 값이 없더라도 특정 Key에 접근 시 지정한 타입으로 Value를 초기화해준다. 우리는 이걸 사용함으로써 특정 시각(키)에만 원하는 값을 저장하여 사용할 수 있다.

 

모기가 입장한 시각에 해당하는 값은 +1을 해주고 퇴장한 시각에 해당하는 값은 -1을 해준다. 특정 시각에 모기 몇 마리가 방에 들어오고 나갔는지 확인하기 위해서다. 주어진 예제에서 시각이 2, 4 일 때 모기가 각 1마리 들어왔고 6일때는 변동이 없으며 10, 16일 때 모기가 각 1마리 나갔다. 

 

이제 모기가 입퇴장한 시각을 오름차순 정렬해서 방에 있는 모기의 수를 셀 것이다. 앞서 각 시각에 대해 모기의 증가 및 증감량을 저장해놨다. 

각 시각에 저장된 값을 더해가면서 모기 수의 최댓값을 구해준다. 최댓값을 갱신했을 때의 시각이 Tem이고, 최댓값인 상태에서 모기 수가 줄어들었을 때 시각이 Txm이 된다. 단, 방에 모기가 최대인 시간이 여러 가지일 수 있기 때문에 Txm은 최댓값이 처음 갱신된 직후에 모기 수가 감소했을 때만 갱신해줘야 한다. 

 

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

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

m, cnt = 0, 0
tem, txm = 0, 0
flag = False
for i in sorted(d.keys()):
    cnt += d[i]
    if cnt > m:
        m = cnt
        tem = i
        flag = True
    elif cnt < m and cnt - d[i] == m and flag:
        txm = i
        flag = False
print(m)
print(tem, txm)