[백준-파이썬] 20440: 니가 싫어 2

문제 보러 가기!

얼마 전에 누적합을 처음 공부하고, 관련된 문제를 풀고 싶어서 스터디 문제에 추가했다.(한 사람 당 한 문제씩 추가하는 방식으로 스터디를 하는 중입니다~)
그런데 단순한 누적합..만으로는 해결할 수 없었다..ㅠㅠ
0 ≤ 모기의 입장 시각 < 모기의 퇴장 시각 ≤ 2,100,000,000... 너무 컸기 때문이다.
그래서 계속 시간 초과, 메모리 초과..와 싸우다가 스터디를 할 때까지 못 풀었다.
스터디원 분께서 설명해주셔서 값, 좌표 압축이라는 아이디어를 처음 알게 되었다! 그 아이디어를 적용하고, 다른 부분도(이것도 아래에서 설명하겠다.) 바꾸니까 문제를 풀 수 있었다 !

전에 코드(시간 초과) 💥

import collections
import sys

input = sys.stdin.readline

N = int(input())
mos_time = tuple(tuple(map(int, input().split())) for _ in range(N))
# mos_check = [0]*(2100000001)
mos_check = collections.defaultdict(int)

max_time = 0
# 모기 출입 시간 체크
for i in range(N):
    check_in, check_out = mos_time[i]
    mos_check[check_in] += 1
    mos_check[check_out] -= 1
    # max_time = max(max_time, check_out)

max_time = max(mos_check.keys())
# 가장 많이 있는 시간대, 그때 몇 마리인지
mos_hot_time = [0, 0]
# mos_cnt = [0] * (max_time + 1)
curr_mos_cnt, next_mos_cnt = 0, 0
max_mos_cnt = 0

for i in range(1, max_time + 1):
    next_mos_cnt = curr_mos_cnt + mos_check[i]
    if next_mos_cnt == 0 : continue
    if next_mos_cnt > max_mos_cnt:
        max_mos_cnt = next_mos_cnt
        mos_hot_time[0] = i  # 시작 시간
    elif next_mos_cnt == max_mos_cnt:
        mos_hot_time[1] = i  # 끝시간 매번 갱신
    curr_mos_cnt = next_mos_cnt

print(max_mos_cnt)
start = mos_hot_time[0]
end = mos_hot_time[1]
print(start, end)

이 코드는 for문에서 1부터 max_time+1까지 하나 하나 살펴본다. 그러면서, 모기가 들어가거나 나갔는지 살펴보면서 처리한다. max_time은 모기가 가장 늦게 나온 시각이 되는 것이니까 최대 21억까지 들어갈 수 있다. 시간 초과 날 만하다..

나중 코드(맞았습니다) 💚

import collections
import sys

input = sys.stdin.readline

N = int(input())
mos_time = list(tuple(map(int, input().split())) for _ in range(N))
mos_time.sort()
# mos_check = [0]*(2100000001)
mos_check = collections.defaultdict(int)

max_time = 0
# 모기 출입 시간 체크
for i in range(N):
    check_in, check_out = mos_time[i]
    mos_check[check_in] += 1
    mos_check[check_out] -= 1
    # max_time = max(max_time, check_out)

max_time = max(mos_check.keys())
# 가장 많이 있는 시간대, 그때 몇 마리인지
mos_hot_time = [0, 0]
# mos_cnt = [0] * (max_time + 1)
curr_mos_cnt, next_mos_cnt = 0, 0
max_mos_cnt = 0
max_first_flag = False

# 모기가 등장할 때만 확인.
mos = list(mos_check.keys())
mos.sort()
for i in mos:
    next_mos_cnt = curr_mos_cnt + mos_check[i]
    if next_mos_cnt > max_mos_cnt:
        max_mos_cnt = next_mos_cnt
        mos_hot_time[0] = i  # 시작 시간
        max_first_flag = True
    elif next_mos_cnt == max_mos_cnt and max_first_flag == True:
        mos_hot_time[1] = i  # 끝시간 매번 갱신
    elif next_mos_cnt < max_mos_cnt and max_first_flag==True:
        mos_hot_time[1] = i
        max_first_flag = False
    curr_mos_cnt = next_mos_cnt

print(max_mos_cnt)
start = mos_hot_time[0]
end = mos_hot_time[1]
print(start, end)

좌표 압축은 딱 중요한 구간이나 숫자만 가지고 있는 기법을 말한다고 한다.

참고
https://jason9319.tistory.com/m/356
https://duzi077.tistory.com/163

음.. 전에 코드에서는 이미 mos_check에서 중요한 값들만 가지고 있긴 했지만, 모든 구간을 보느라고 너무 시간이 오래 걸렸다. 그래서 모든 구간을 보지 말고, 딱 모기가 등장할 때만 확인해주는 식으로 바꿨더니 맞았다 !

그리고 전에 코드에서는 max_first_flag를 두지 않았다. 이게 왜 문제인지 살펴보겠다.

그러면 위 그림 같은 상황에서 이상한 답이 나온다.
앞부분에도 모기가 3마리였다가, 다시 2마리 -> 1마리만 있다가 나중에 3마리인 상황이 다시 나온다. 만약 max_first_flag가 없다면? 그림에서 나중에 3마리인 상황에서도, 모기가 가장 많이 있는 시간대(mos_hot_time)의 끝나는 시각을 계속 업데이트한다. 그러면 모기가 가장 많이 있는 시간대(그 시간대가 여러 개일 경우, 가장 빠른 시작 시각 기준으로 출력)는 분홍색 구간이지만, 주황색 구간이 답으로 나온다.
그래서 최대 수의 모기가 있는 것이 처음인지, 아닌지를 담는 max_first_flag를 만들었다. 가장 많은 모기를 만나다가, 모기 수가 줄어들면(즉 정답 구간이 끝나면) max_first_flag를 False로 바꿨다. 나중에 같은 모기 수가 있는 구간을 만나더라도, max_first_flag가 False라면, 정답 구간의 끝 시각을 업데이트하지 않았다.