김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 21774 가희와 로그 파일 파이썬(Python)

문제 링크

파싱의 탈을 쓴 그냥 이분탐색 문제.
날짜, 시간 파싱 문제라 별 생각 없이 datetime.strptime()을 했는데 TLE가 났다.
시간을 재보니 datetime.strptime()이 심각하게 느리더라.
그래서 일일히 초로 변환해서 파싱을 해야하나 생각하다가 시험삼아 datetime() 객체 안에 정수로 변환한 숫자들을 넣어주었더니 훨씬 빨라졌다.
그렇게 의기양양하게 문제를 풀고 나서 찾아보니, 이 문제 파싱을 할 필요가 없다…
생각해보면 어차피 날짜, 시간 배열이 연, 월, 일, 시, 분, 초 순서대로고 0으로 패딩도 되어있다면, 문자열 자체의 사전순 배열이 시간 순서대로의 배열과 일치한다.
여기서 딱히 구체적인 시간은 알 필요 없고, 그냥 시간의 선후관계(대소관계)만이 중요하므로 그냥 파싱을 안 하고 문자열 자체로 비교해도 된다.
습관에 따른 코딩이 얼마나 무서운지를 보여주는 예시.
그리고, 단순히 범위를 찾기 위해 선형탐색을 하면 당연히 시간초과이므로 정렬된 데이터를 대상으로 이분탐색으로 시작점과 끝점을 찾아준다.
이와 관련하여 이 문제에서는 하한(Lower Bound)과 상한(Upper Bound)를 사용할 수 있다.
이분탐색에서 하한과 상한이란 각각 “원하는 값 이상의 값이 처음 나오는 인덱스”와 “원하는 값 초과의 값이 처음 나오는 인덱스”이다.
시작점 이상의 시간부터 끝점 초과의 시간까지가 원하는 로그들이므로 이분탐색을 통해 로그 레벨별로 해당 값들을 구하고 더해서 출력하면 된다.
bisect라는 이분탐색 모듈도 있던데, 다음엔 그걸 써보도록 해야겠다.

#!python

from sys import stdin
from datetime import datetime
input = stdin.readline

# 시간 파싱 함수
# datetime.strptime()보다 datetime()이 훨씬 빠르다
# 그런데 사실 파싱을 안 해도 된다...
def parse(dstr):
    y, m, d = map(int, (dstr[0:4], dstr[5:7], dstr[8:10]))
    h, mi, s = map(int, (dstr[11:13], dstr[14:16], dstr[17:]))
    return datetime(y, m, d, h, mi, s)

# lower bound 탐색
# 주어진 값 이상의 값이 최초로 등장하는 인덱스 반환
def search_low(iter, val):
    l, r = 0, len(iter)
    while l < r:
        m = (l + r) // 2
        if val <= iter[m]:
            r = m
        else:
            l = m + 1
    return l

# upper bound 탐색
# 주어진 값보다 큰 값이 최초로 등장하는 인덱스 반환
def search_high(iter, val):
    l, r = 0, len(iter)
    while l < r:
        m = (l + r) // 2
        if val >= iter[m]:
            l = m + 1
        else:
            r = m
    return l

n, q = map(int, input().split())
log = [[] for _ in range(6)]

# 로그 파싱하여 레벨별로 저장
for _ in range(n):
    dt, lvl = input().split('#')
    dt, lvl = parse(dt), int(lvl)
    log[lvl-1].append(dt)

# 쿼리 파싱하여 총합 출력
for _ in range(q):
    start, end, lvl = input().split('#')
    start, end = map(parse, (start, end))
    lvl = int(lvl)

    # 해당 레벨 이상의 모든 레벨에 대해 이분탐색
    ans = 0
    for i in range(lvl - 1, 6):
        l = search_low(log[i], start)
        r = search_high(log[i], end)
        ans += r - l
    print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑