문제
송훈이는 로봇 동아리 회원이다. 로봇 동아리에서 필요한 부품이 있을 경우 자유롭게 빌려서 쓰고 다시 돌려놓으면 된다.
하지만 부품 정리를 하다가 부품 관리가 너무 힘들어져 새로운 시스템을 도입하려고 한다.
부품을 빌려갈 경우 부품 대여장에 정보를 반드시 작성해야한다. 또한 빌려간 부품을 반납 할 경우에도 부품 대여장에 정보를 작성해야한다.
또한 대여기간을 정하고 대여기간을 넘길 경우 1분당 벌금을 부여하도록 하는 시스템이다.
만약 대여기간이 5분, 1분당 벌금이 5원이라 했을 때 대여한 시각이 2021년 1월 1일 1시 5분이라면 2021년 1월 1일 1시 10분까지 반납해야한다.
2021년 1월 1일 1시 14분에 반납을 했다면 4분 늦었기 때문에 벌금을 20원을 내야한다.
부품 대여장에 쓰는 형식은 아래와 같다.
yyyy-MM-dd hh:mm [부품 이름] [동아리 회원 닉네임]아래는 예시를 위한 부품 대여장에 작성된 정보이다. 대여기간이 5분, 벌금은 1원이라 가정하자.
2021-01-01 09:12 arduino tony9402
2021-01-01 09:13 monitor chansol
2021-01-01 09:18 arduino tony9402
2021-01-01 09:18 monitor chansol위의 정보를 정리하면 아래와 같다.
tony9402가 2021년 1월 1일 오전 9시 12분에 arduino를 빌렸다.
chansol이 2021년 1월 1일 오전 9시 13분에 monitor를 빌렸다.
tony9402가 2021년 1월 1일 오전 9시 18분에 arduino를 반납했다.
chansol이 2021년 1월 1일 오전 9시 18분에 monitor를 반납했다.tony9402는 1분 늦게 반납했기 때문에 벌금 1원을 내야한다.
부품을 대여할 때 지켜야 하는 조건이 있다.
- 한 사람이 같은 종류의 부품을 두개 이상 대여하고 있는 상태일 수 없다.
- 한 사람이 같은 시각에 서로 다른 종류의 부품들을 대여하는 것이 가능하다.
- 같은 사람이더라도, 대여 기간은 부품마다 별도로 적용된다.
풀이
진짜 문제를 안읽고 풀면 어떻게 되는 지 반성할 수 있는 좋은 사례.
시간 순으로 입력이 들어오는데 굳이 처리를 따로 해줬다. 시간에 따라 heapq를 사용해서 꺼내오는 방식을 사용했는데,
당연히 안됐다. 아래는 삽질 코드
import sys
from heapq import heappush, heappop
from datetime import datetime, timedelta
def si(): return sys.stdin.readline()
def msis(): return map(str, si().split())
n, l, f = msis()
n, f, penalty = int(n), int(f), timedelta(days=int(l[:3]), hours=int(l[4:6]), minutes=int(l[7:]))
minute = timedelta(minutes=1)
p_table = {}
f_table = {}
heap = []
for _ in range(n):
date, time, part, nickname = si().split()
date = datetime.strptime(date + ' ' + time, '%Y-%m-%d %H:%M')
p_table[part] = []
f_table[nickname] = 0
heappush(heap, (date, part, nickname))
while heap:
d, p, m = heappop(heap)
flag = True
for lst in p_table[p]:
if m == lst[1]:
flag = False
period = d - lst[0]
if period > penalty:
f_table[m] += ((period - penalty) // minute) * f
p_table[p].remove(lst)
break
if flag:
p_table[p].append((d, m))
result = [(k, v) for k, v in f_table.items() if v]
result.sort(key=lambda x: x[0])
for nick, val in result:
print(nick, val)문제를 다시 읽고, 단단히 잘못 하고 있다는 것을 알고 다시 풀었다.
timedelta를 이용해서 날짜 연산을 해주는 방식으로 진행했고, 딕셔너리를 이용해 빌려간 요청인지 빌리는 요청인지 구분.
알고리즘 없는 구현문제였던 것 같다.
import sys
from collections import defaultdict
from datetime import datetime, timedelta
def si(): return sys.stdin.readline()
def msis(): return map(str, si().split())
n, l, f = msis()
n, f, maximum = int(n), int(f), timedelta(days=int(l[:3]), hours=int(l[4:6]), minutes=int(l[7:]))
minute = timedelta(minutes=1)
table = defaultdict(dict)
p_table = defaultdict()
for _ in range(n):
line = si()
now = datetime.strptime(line[:16], '%Y-%m-%d %H:%M')
part, name = line[16:].split()
if not p_table.get(name):
p_table[name] = 0
if table[name].get(part):
period = now - table[name][part]
if period > maximum:
p_table[name] += ((period - maximum) // minute) * f
del table[name][part]
else:
table[name][part] = now
ret = [(k, v) for k, v in p_table.items() if v]
if ret:
for name, val in sorted(ret, key=lambda x: x[0]):
print(name, val)
else:
print(-1)
