김낭만

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

백준(BOJ) 21942 부품 대여장 파이썬(Python)

문제 링크

시간을 파싱하고 해시맵(또는 해시테이블, 파이썬에서는 딕셔너리)을 사용하는 문제.
파이썬에서는 딕셔너리(dict 객체)도, 시간의 파싱과 계산(datetime과 timedelta 객체)도 모두 구현되어 있으므로 쉽게 풀 수 있다.
풀고 나서 보니 시간이 빠른 풀이는 datetime 모듈을 쓰지 않고 직접 산술적으로 곱해서 계산하는 풀이던데, 아마 datetime 객체 간 연산보다 그냥 분 단위 정수 연산이 훨씬 빨라서일 것이다.
아무튼, 파싱은 datetime.strptime()으로 할 수 있고, 처음에 주어지는 대여시간 l만 timedelta 객체에 파싱해서 넣으면 되는데 이는 별로 어렵지 않다.
그 후엔 딕셔너리를 만들어서 대여, 반납 상태를 확인하고, 시간이 지난 경우 벌금을 계산해두었다가 나중에 사전 순으로 출력하면 된다.
처음에 문제를 풀 때 반납하는 경우 벌금만 계산하고 딕셔너리에서 지우는 것을 잊었는데, 그 경우 같은 사람이 같은 물품을 다시 빌리는 경우 문제가 될 수 있으므로 이 경우를 위해 딕셔너리에서 pop()을 해줘야 한다.

#!python

from sys import stdin
from datetime import datetime, timedelta
from collections import defaultdict
input = stdin.readline

n, l, f = input().split()
n, f = map(int, (n, f))
# l은 대여 기간이므로 타임델타(시간의 차이) 객체로
l = timedelta(days=int(l[0:3]), hours=int(l[4:6]), minutes=int(l[7:]))
# 부품 대여장 딕셔너리
borrow = {}
# 벌금 딕셔너리
fine = defaultdict(int)

for _ in range(n):
    t1, t2, p, m = input().split()
    # 시간 파싱
    t = datetime.strptime(t1 + ' ' + t2, '%Y-%m-%d %H:%M')
    # 만약 이미 빌려간 경우라면(즉 반납이라면)
    if (p, m) in borrow:
        # 반납했으므로 대여장에서 지운다
        borrow.pop((p, m))
        # 그 이후 연체반납이라면 벌금을 저장한다
        if t - borrow[p, m] > l:
            fine[m] += int((t - borrow[p, m] - l).total_seconds() / 60 * f)
    else:
        # 대여하는 경우라면 대여장에 대여 날짜를 기록한다
        borrow[p, m] = t

# 사전순이므로 키를 정렬해서 출력
# 벌금 딕셔너리가 비었다면 -1 출력
for key in sorted(fine):
    print(key, fine[key])
if not fine:
    print(-1)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑