(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 9203 호텔 예약 파이썬(Python)
날짜 파싱하고 스위핑(Sweeping) 알고리즘을 사용하는 문제.
사실 이 문제를 풀고 나서 스위핑 알고리즘을 처음 들어본 것 같다.
스위핑 알고리즘이란 말은 별 게 아니고, 입력을 한 쪽부터 훑는다는, 즉 순회한다는 뜻이다.
그래서 이 문제는 어떻게 풀 수 있느냐 하면, 먼저 각 테스트케이스별로 체크인, 아웃 시간을 기록한다.
파이썬이므로 datetime 객체를 이용하면 간단하고, 이때, 체크아웃 시간에는 청소 시간을 더해줬다.
청소 시간에도 방이 가용하지 않으므로 점유중인 것이나 마찬가지이기 때문이다. 다시 말해서 지금 체크아웃을 하고 30분 청소를 하나, 30분 후에 체크아웃을 하고 청소를 안 하나 시간적으로는 같다는 의미이다.
당연히 반대로 체크인 시간에서 청소 시간을 빼줘도 될 것이다.
그 이후에는 기록을 정렬하는데, 이때는 체크인과 체크아웃을 구분하기 위해 튜플로 저장한다.
이 경우, 튜플의 1번 인덱스가 1이면 필요한 방이 1개 늘어난다는 뜻이고, 따라서 체크인이며, 반대로 -1이면 필요한 방이 1개 감소한다는 뜻이므로 체크아웃이다.
이후 기록된 리스트를 정렬하면, 먼저 튜플의 0번 인덱스, 즉 시간 순으로 정렬되대, 같은 시간에 대해서는 1번 인덱스가 음수인 체크아웃이 먼저 등장할 것이다.
이는 동시에 체크인과 체크아웃이 일어나면 체크아웃을 먼저 처리한다는 것이다.
여기까지 기록이 끝났으면, 이제 리스트를 순회하면 된다.
현재 방과 필요한 방 모두 1개에서 시작해서, 현재 방이 부족해지면 현재 방과 필요한 방에 1을 더하는 식으로 작동한다.
체크인을 할 때마다 현재 방 수가 1씩 감소하고, 체크아웃을 할 때마다 현재 방 수가 1씩 증가한다.
리스트를 순회한 후 필요한 방 개수를 출력해주면 된다.
#!python
from sys import stdin
from datetime import datetime, timedelta
input = stdin.readline
# 시간을 파싱해서 datetime() 객체로 변환하는 함수
# 만약 체크아웃 시간이라면 to_clean이 참이 되는데, 이 경우 청소시간을 더해서 종료시간을 정해준다
def parse(date, time, to_clean):
if to_clean:
return datetime(*map(int, (date[:4], date[5:7], date[8:], time[:2], time[3:]))) + timedelta(minutes=c)
return datetime(*map(int, (date[:4], date[5:7], date[8:], time[:2], time[3:])))
t = int(input())
for _ in range(t):
# 로그는 체크인, 체크아웃을 기록하는 장부
log = []
b, c = map(int, input().split())
for _ in range(b):
# in1, in2 : 체크인 날짜, 시간
# out1, out2 : 체크아웃 날짜, 시간
_, in1, in2, out1, out2 = input().split()
# 파싱해서 datetime() 객체로 바꾸되, 체크아웃 시간에는 청소 시간을 더해준다
# 왜냐하면 청소시간동안 방을 못 쓰는 건 똑같기 때문에
chkin = parse(in1, in2, False)
chkout = parse(out1, out2, True)
# 체크인인 경우 1, 체크아웃인 경우 -1로 표기한다
log.append((chkin, 1))
log.append((chkout, -1))
# 정렬을 하게 되면 시간 순서대로 기록이 정리된다
# 또한, 같은 시간에 대해 체크아웃이 체크인보다 먼저 등장하므로 동시에 체크인/아웃 한 경우 방 개수가 알맞게 계산된다
log.sort()
# need는 필요한 총 방 개수
# rooms는 현재 남은 방 개수
need = 1
rooms = 1
# 로그를 순회하면서
for _, rd in log:
# rd는 room delta, 즉 필요한 방 수 변화
# 체크인인 경우 1이 빼지므로 방 하나가 사라짐
# 체크아웃인 경우 -1이 빼지므로 방 하나가 생겨남
rooms -= rd
# 그 후 만약 방이 -1개라면
# 즉, 방이 0개였다가 체크인을 당해서 방이 -1개가 되면
if rooms == -1:
# 필요한 방이 하나 더 있는 것이므로 늘려준다
rooms += 1
need += 1
# 필요한 총 방 개수 출력
print(need)
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...