[BOJ_Python] 20055. 컨베이어 벨트 위의 로봇

문제

https://www.acmicpc.net/problem/20055

 

사용 알고리즘

구현, 순환 큐(deque - rotate)

 

풀이

코드 흐름

1. belt 회전

    - belt의 start 시점 이동

    - belt 회전에 따른 로봇 이동

      이때의 로봇이동은 belt와 함께 가는 것이기 때문에 내구도가 약화되지 않음

      또한, 내리는 지점에 도달하였으면 박스를 내리며, 시작지점은 비어있음

2. 로봇의 이동

    - 이동할 곳의 내구도, 현재 위치의 로봇 여부, 이동할 곳의 로봇 여부 확인

    - 이동이 가능할 경우 로봇 이동과 내구도 약화 진행

    - 내리는 지점 도달 여부 확인 및 로봇 내리기 진행

3. 새로운 상자 올리기

    - 내구도 확인 후 새로운 상자 올리기

4. belt의 내구도가 0인 갯수 확인

 

후기

1. 메모리 관리 - rotate vs. (for문을 활용한) index

문제를 처음 보았을 때, 가장 먼저 rotate 함수가 생각났지만,

조건과 시간을 보고 인덱스로 접근을 결정하였다. 

 

rotate를 사용하면 코드가 직관적이며 직접적인 위치 계산을 피할 수 있기 때문에

가독성이 올라가고, 잔 실수 없이 편리하게 풀이가 가능하다.

하지만, deque 구조를 사용하기 때문에 리스트 전체를 회전하며 메모리 사용이 증가한다.

이런 방식은 회전 연산이 빈번한 경우 성능 저하가 예상된다.

해당 문제에서는 로봇도 rotate, belt도 rotate를 매번 진행하기 때문에 빈번하였다.

 

때문에 인덱스 이동 방식으로 문제를 풀이하였다. 

 

2. 시간 관리 - 슬라이싱 vs. for 루프

하지만 위의 방식으로는 python3로 제출 시 시간초과가 발생하였다.

 

이는 rotate를 사용하지 않아 시간을 관리한다 해놓고 for문을 돌고있었기 때문이다.

for문을 사용하게 되면 메모리 측면에서는 좋아질 수 있더라도

결국 하나씩 이동하는 것이기 때문에 시간적으로 좋지 않다.

for cur in range(N - 2, 0, -1):
    robots[cur] = robots[cur - 1]

 

때문에 슬라이싱을 선택하였다.

이 방식은 하나하나 돌면서 진행하지 않기 때문에

속도 측면에서는 효율적이지만, 새로운 리스트를 만들기 때문에 메모리의 추가 사용이 단점인 방식이다.

robots = [0] + robots[:-1]
robots[N - 1] = 0

 

3. 돌고돌아 메모리와 시간 통합 관리 - 슬라이싱 vs. rotate

하지만, for문을 사용하지 않고, 슬라이싱을 사용한다면 1번의 메모리 관리를 한 이유가 없어진다.

 

슬라이싱은 새로운 리스트를 생성하기 때문에 메모리 측면에서 좋은 선택은 아니기 때문이다.

때문에 메모리와 시간 모두를 고려하여 슬라이싱과 rotate를 다시 비교하면

deque는 회전 연산이 매우 빠르게 진행되며 메모리도 효율적으로 관리 할 수 있다.

이러한 이유로 rotate를 선택하여 문제를 해결하였다.

 

추가)

슬라이싱이 매번 새로운 리스트를 생성하여 메모리 측면에서도 안좋을 것이라 예상하였지만,

오히려 슬라이싱 방식이 메모리에서 미세하게 좋은 쪽으로 나타났다.

이는 리스트를 생성하여 메모리를 사용하지만, 

리스트 크기가 고정되어 있기 때문으로 예상된다.

deque의 경우 동적으로 크기를 조정(append, pop 등)으로 크기를 조정 할 수 있는 장점이 있지만,

메모리 오버헤드가 추가 될 수 있다고 한다.

 

코드

1. rotate 활용 코드

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
belt = deque(map(int, input().split()))
robots = deque([0] * N)

cnt = 0

while True:
    # 0. 횟수 증가
    cnt += 1

    # 1. 벨트 회전 (deque.rotate(1) 사용)
    belt.rotate(1)
    # 1-2. 벨트 회전에 따른 로봇 이동
    robots.rotate(1)
    robots[N-1] = 0

    # 2. 로봇 이동
    for cur in range(N - 1, 0, -1):
        if (belt[cur] > 0
            and robots[cur] == 0 and robots[cur - 1] == 1):
            # 로봇 이동
            robots[cur] = robots[cur - 1]
            robots[cur - 1] = 0
            # 내구도 약화
            belt[cur] -= 1

    # 2-2. 로봇 내리기
    robots[N - 1] = 0

    # 3. 내구도 확인 후 상자 올리기
    if belt[0] > 0:
        robots[0] = 1
        belt[0] -= 1

    # 4. 내구도 0인 자리 갯수 확인
    if belt.count(0) >= K:
        print(cnt)
        break

 

2. 슬라이싱 활용 코드

# 1 ~ 2만 위의 코드와 변동

    # 1. 벨트 회전
    start = (start - 1) % (2 * N)

    # 1-2. 벨트 회전에 따른 로봇 이동
    robots = [0] + robots[:-1]
    robots[N - 1] = 0

    # 2. 로봇 이동
    for cur in range(N - 1, 0, -1):
        # 벨트의 내구도, 현재 위치의 로봇 여부 확인
        if (belt[(start + cur) % (2 * N)] > 0
            and robots[cur] == 0 and robots[cur - 1] == 1):
            # 로봇 이동
            robots[cur] = robots[cur - 1]
            robots[cur - 1] = 0
            # 내구도 약화
            belt[(start + cur) % (2 * N)] -= 1
    # 2-2. 로봇 내리기
    robots[N - 1] = 0

 

3. for문 활용 코드

# 1-2만 슬라이싱과 다름

    # 1-2. 벨트 회전에 따른 로봇 이동
    for cur in range(N - 2, 0, -1):
        robots[cur] = robots[cur - 1]
    robots[0] = 0

결과

위 - rotate를 사용한 버전 

아래 - 슬라이싱을 사용한 버전

 

추가) for문 사용 버전