[Algorithm🧬] 백준 2065 : 나룻배

문제

이해해야하는 코드.

import sys
from collections import deque

readl = sys.stdin.readline

# 최대 m 명, 가는데 t 시간, N 손님.
m, t, n = map(int, readl().split())
order = [readl().split() for _ in range(n)]
order = [[i, int(o[0]), o[1]] for i, o in enumerate(order)]


# 해당 시간에 한쪽에 와서 있는 사람 전부 큐에 left, right 나눠서 넣음.
def passanger_At_Stop(totalTime, stop, i):
    while i < n and order[i][1] <= totalTime:
        side = (order[i][2] == "right")
        stop[side].append(order[i][0])
        i += 1
    return i

# 배에 탄다.
def take_ship(ship, stop, ship_side):
    while len(ship) < m and stop[ship_side]:
        ship.append(stop[ship_side].popleft())

# 배에서 내림.
def take_off_ship(totalTime, arr, ship, cnt):
    while ship:
        arr[ship.popleft()] = totalTime
        cnt += 1
    return cnt


leftq = deque()
rightq = deque()
stop = [leftq, rightq]


ship = deque()

ship_side = 0 # 왼쪽에서 시작
totalTime = 0
i = 0
cnt = 0

arr = [0] * n # 해당 index 에 해당하는게 언제 도착하는지 알아야함

while cnt < n:
    # 지금 시간에 대해서 태우고
    i = passanger_At_Stop(totalTime, stop, i)
    take_ship(ship, stop, ship_side)

    # 만약 배도 비어있고 양쪽에 기다리는 승객이 없으면
    # totalTime 을 갱신하고 태움. (움직이지 않고 계속 기다리는걸 표현)
    if len(ship) == 0 and len(stop[0]) == 0 and len(stop[1]) == 0 and i < n:
        totalTime = order[i][1]
        i = passanger_At_Stop(totalTime, stop, i)
        take_ship(ship, stop, ship_side)

    # totalTime 갱신.
    ship_side = 0 if ship_side else 1
    totalTime += t

    # 내린다.
    cnt = take_off_ship(totalTime, arr, ship, cnt)

print(*arr, sep='\n')

함수로 쪼개지 않은 코드

import sys
from collections import deque

readl = sys.stdin.readline

m, t, n = map(int, readl().split())
order = [readl().split() for _ in range(n)]
order = [[i, int(o[0]), o[1]] for i, o in enumerate(order)]


stop = [deque(), deque()] # leftq, rightq
ship = deque()
ship_side = 0 # left 에서 시작.
i = 0
current = 0
res = [0] * n
cnt = 0 # 내린 사람 카운트

while cnt < n:

    # 현재 시간보다 작은 것을 대기열에 넣음.
    while i < n and current >= order[i][1]:
        side = (order[i][2] == "right")
        stop[side].append(order[i][0])
        i += 1

    # 현재 배가 있는 곳의 대기열을 배에 태움.
    while len(ship) < m and stop[ship_side]:
        ship.append(stop[ship_side].popleft())

    if len(ship) == 0 and len(stop[0]) == 0 and len(stop[1]) == 0 and i < n:
        # 만약 해당 시간에 손님이 계속 없으면 다음 손님이 올때까지 기다림
        current = order[i][1]

        # 동시에 여러게 올 수도 있으니까.
        # 현재 시간과 같은 것을 대기열에 넣음.
        while i < n and current >= order[i][1]:
            side = (order[i][2] == "right")
            stop[side].append(order[i][0])
            i += 1

        # 현재 배가 있는 곳의 대기열을 배에 태움.
        while len(ship) < m and stop[ship_side]:
            ship.append(stop[ship_side].popleft())

    ship_side = 0 if ship_side else 1
    current += t

    while ship:
        res[ship.popleft()] = current
        cnt += 1

print(*res, sep='\n')

안되는 코드.

import sys
from collections import deque

readl = sys.stdin.readline

# 최대 m 명, 가는데 t 시간, N 손님.
m, t, n = map(int, readl().split())
order = [readl().split() for i, s in range(n)]
order = [[i, int(o[0]), o[1]] for i, o in enumerate(order)]

leftq = deque()
rightq = deque()

arr = [0] * n # 해당 index 에 해당하는게 언제 도착하는지 알아야함
ship = deque()

left = True
totalTime = 0
i = 0

while i < n:
    time, pos = int(order[i][0]), order[i][1]

    # 첫번째 도착하는 건 넣고 시작
    if i == 0:
        left = (pos == "left")
        totalTime += time + 0 if left else t
        if left:
            leftq.append((i, time, pos))
        else:
            rightq.append((i, time, pos))
        i += 1


    time, pos = int(order[i][0]), order[i][1]

    # t 초 간격으로 같은 시간에 도착한거 다 큐에 넣고
    while i < n and totalTime >= int(order[i][0]):
        time, pos = int(order[i][0]), order[i][1]
        if pos == "left":
            leftq.append((i, time, pos))
        else:
            rightq.append((i, time, pos))

        i += 1

    print("in", leftq, rightq, totalTime)

    # 왼쪽에 있으면 왼쪽큐에서 빼가고
    if left and leftq:
        left = not left
        for j in range(m):
            if ship:
                index, _, _ = ship.popleft()
                arr[index] = totalTime
        for j in range(m):
            if leftq:
                ship.append(leftq.popleft())
    # 왼쪽에 있지만 왼쪽 큐가 비어있고 오른쪽 큐에 손님이 있으면 오른쪽으로
    elif left and not leftq and rightq:
        left = not left
        for j in range(m):
            if ship:
                index, _, _ = ship.popleft()
                arr[index] = totalTime

    # 오른쪽에 있으면 오른쪽 큐에서 빼가고
    if not left and rightq:
        left = not left
        for j in range(m):
            if ship:
                index, _, _ = ship.popleft()
                arr[index] = totalTime
        for j in range(m):
            if rightq:
                ship.append(rightq.popleft())
    # 오른쪽에 있지만 오른쪽 큐가 비어있고 왼쪽 큐에 손님이 있으면 왼쪽으로
    elif not left and not rightq and leftq:
        left = not left
        for j in range(m):
            if ship:
                index, _, _ = ship.popleft()
                arr[index] = totalTime

    totalTime += t
    print("out", leftq, rightq, totalTime)

arr[-1] = totalTime + t


print(*arr, sep='\n')