[BOJ 21774] - 가희와 로그 파일

먼저 입력의 형태를 한눈에 봤을 때, 주어진 시간을 초 단위로 파싱하는 로직을 짜야겠다는 생각이 들어 파싱을 진행했습니다.

2 2
2021-04-05 17:17:11#1
2021-04-05 17:18:11#2
2021-04-05 17:17:11#2021-04-05 17:18:11#1
2021-04-05 17:18:11#2021-04-05 17:19:11#3

def parseYearToSecond(year):
    if year == 2000 or year == 2004 or year == 2008 or year == 2012 or year == 2016 or year == 2020:
        return year * 60 * 60 * 24 * 366
    else:
        return year * 60 * 60 * 24 * 365


def parseMonthToSecond(month):
    if month == 1:
        return 0
    elif month == 2:
        return 31 * 60 * 60 * 24
    elif month == 3:
        return 59 * 60 * 60 * 24
    elif month == 4:
        return 90 * 60 * 60 * 24
    elif month == 5:
        return 120 * 60 * 60 * 24
    elif month == 6:
        return 151 * 60 * 60 * 24
    elif month == 7:
        return 181 * 60 * 60 * 24
    elif month == 8:
        return 212 * 60 * 60 * 24
    elif month == 9:
        return 243 * 60 * 60 * 24
    elif month == 10:
        return 273 * 60 * 60 * 24
    elif month == 11:
        return 304 * 60 * 60 * 24
    elif month == 12:
        return 334 * 60 * 60 * 24


def parseTimeToSecond(time):
    second = 0
    second += (parseYearToSecond(int(time[0:4])) + parseMonthToSecond(int(time[5:7])) + int(
        time[8:10]) * 60 * 60 * 24 + int(time[11:13]) * 60 * 60 + int(time[14:16]) * 60 + int(time[17:19]))
    return second

대략 윤년과 각 월 등을 계산하고 이를 모두 더한 초 단위의 시간을 리턴해주는 함수인데...
후술하겠지만 이 작업은 불필요할뿐만 아니라, 오히려 테스트케이스의 범위 때문인지 시간 초과의 원인이 되었습니다.

---

이제 핵심 로직을 소개해 보겠습니다.
주어진 시간 (Ex. 2021-04-05 17:17:11 ~ 2021-04-05 17:18:11) 사이의 값을 찾고, 사잇값들 중에서도 특정 레벨보다 낮은 값을 찾아야 합니다.

그런데 "같은 시각에 여러 개의 로그가 존재할 수도 있다" 는 조건이 있습니다.
따라서 {"2021-04-12 17:10:11" : 2} 처럼 날짜값을 키로 갖는 map 자료형을 사용할 수도 없고, {2 : "2021-04-12 17:10:11" } 처럼 맵핑을 반대로 할 수도 없습니다.

이럴 때 사용할 수 있는, 모두가 알고 있는 기가 막힌 도구가 하나 있습니다.
바로 배열입니다.

---

조건을 잘 읽어보시면 찾고자 하는 로그의 레벨은 1 <= 레벨 <= 6 으로 범위가 굉장히 작음을 알 수 있었는데요, 이를 이용해 1 ~ 6까지의 레벨을 인덱스로 갖는 배열을 만들고, 각 인덱스의 내부에 해당 레벨을 갖는 날짜들의 배열을 추가합니다.

// 0번 인덱스는 None 처리하고, 1 ~ 6번 인덱스에 담긴 배열은
// 각 인덱스에 해당하는 로그값을 갖는 날짜의 배열입니다.
// Ex. 2021-06-28#2 => 2번째 인덱스에 있는 배열에 2021-06-28 을 추가함.

[None, ["2021-05-28"], ["2021-06-28"], ["2021-07-28", "2021-07-30"], ["2021-08-28"], ["2021-09-28"]]

이제 주어진 레벨 ~ 6번째 배열을 탐색해, 주어진 날짜 범위 안에 있는 값의 개수를 세기만 하면 됩니다.

---

저는 처음에는 단순히 이중 for문을 사용해 탐색을 진행했는데, 아무래도 Q의 범위가 1 ≤ Q ≤ 2×10^5 이고, 로그 배열에 담긴 로그의 숫자도 1 ≤ N ≤ 2×10^5인 까닭에 이렇게는 문제를 풀 수 없다는 것을 알 수 있었습니다.

for _ in range(N):
    time, level = input().split('#')

    logList[int(level)].append(time)

for _ in range(Q):
    start, end, level = input().split("#")
    for i in range(int(level), 7):
        for j in logList[i]:
            if start <= j <= end:
                cnt += 1

그래서 문제 참고에 적혀있던 이진 탐색 기반의 upper_bound 와 lower_bound 개념을 사용해야만 한다는 것은 알았는데, 이는 파이썬의 bisect 모듈에 구현되어 있는 것을 확인할 수 있었습니다.

from bisect import bisect_left, bisect_right

numberList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 5

# numberList 리스트 중, n의 위치에서 가장 가까운 왼쪽 인덱스를 반환함.
print(bisect_left(numberList, n)) # 5

# numberList 리스트 중, n의 위치에서 가장 가까운 오른쪽 인덱스를 반환함.
print(bisect_right(numberList, n)) # 6

그리고 upper_bound 와 lower_bound(bisect_left, bisect_right) 의 진가는 바로, lower_bound의 인덱스에서 upper_bound의 인덱스를 빼면 조건을 만족하는 구간에 속한 원소의 개수를 마법처럼 구할 수 있다는 것입니다.

from bisect import bisect_left, bisect_right

nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 7 이상 9 이하에 존재하는 값의 수를 출력합니다.
print(bisect_right(nums, 9) - bisect_left(nums, 7)) # 3 (7, 8, 9 있으므로)

그렇게 완성된 코드입니다.
윤년 및 월에 따른 초를 계산하는 코드는 날짜 정보를 그냥 전부 문자열로 비교해도 차이가 전혀 없기 때문에 오히려 불필요한 시간을 잡아먹어 제거했습니다. (실제로 시간 -> 초 로직을 포함했을 때는 시간 초과가 발생했는데, 이를 제거하니 통과에 성공했습니다.)

import sys
import bisect

logList = [None, [], [], [], [], [], []]
cnt = 0
input = sys.stdin.readline


def parseTimeString(times):
    return times[:4]+times[5:7]+times[8:10]+times[11:13]+times[14:16]+times[17:19]


N, Q = map(int, input().split())

for _ in range(N):
    time, level = input().split('#')
    logList[int(level)].append(parseTimeString(time))

for _ in range(Q):
    start, end, level = input().split("#")
    for i in range(int(level), 7):
        s_ind = bisect.bisect_left(logList[i], parseTimeString(start))
        print(s_ind)
        e_ind = bisect.bisect_right(logList[i], parseTimeString(end))
        cnt += (e_ind-s_ind)
    print(cnt)
    cnt = 0

The End!