[백준-골드5] 20055번 컨베이어 벨트 위의 로봇(구현, 파이썬)

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

20055번: 컨베이어 벨트 위의 로봇

[시간 초과 원인]

- 직접 rotations 함수를 만들어서 회전시켰다. 이 때, 시간복잡도는 O(N*2)

- deque의 rotate를 이용하니까 해결,,,

- 그리고 문제에서 0이 K이상이면 종료하라했는데, 나는 잘못 읽어서 K일때 종료 조건을 넣어서 시간초과가 났었다.

deque의 rotate

<내 코드>

- 입력을 deque로 받고, 로봇의 위치를 나타낼 큐도 설정했다.

- 이 때 로봇은 (N-1)에 도달하면 내릴것이기 때문에 길이를 n으로 지정했다.

- 문제에서 주어진 조건을 차례대로 수행한다.

- 벨트, 로봇을 회전한 후 로봇이 내릴 위치에 도달했으면 내려준다.

- 그리고 로봇이 조건에 맞춰 이동한다. 내릴 칸의 바로 전 칸부터 맨 앞까지 차례대로 확인해주고

   로봇의 위치르 변경한 후 내구도를 1감소시킨다.

- 또 이 때도 로봇이 움직였으므로 내릴 위치에 로봇이 있으면 바로 내려준다.

- 그리고 첫번째 칸에 로봇을 올릴 수 있으면 올려주고, 내구도를 1 감소시킨다.

- 동작이 끝나면 step을 하나씩 증가시키고, belt의 0의 갯수가 K이상일때 종료한다.

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
belt = deque(map(int, sys.stdin.readline().split()))
         
step = 0
robot = deque([False]*(n))

while True:   
    # 1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전
    belt.rotate(1)
    robot.rotate(1)
    robot[-1] = False 
        
    # 2. 가장 먼저 벨트에 올라간 로봇부터 벨트가 회전하는 방향으로 이동 할 수 있다면 이동
    #   - 로봇이 이동하기 위해 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상
    for i in range(n-2, -1,-1):
        if robot[i] and not robot[i+1] and belt[i+1]>0: # 현재 위치에 로봇이 있고
                robot[i] = False
                robot[i+1] = True
                belt[i+1] -=1 #내구도 감소
    robot[-1] = False #로봇 내림
    
    # 3. 로봇 올림
    if robot[0] == False and belt[0]>0:
        robot[0] = True
        belt[0]-=1

                  
    cnt = belt.count(0)
    step+=1
    # 4. 종료 조건
    if cnt >=k:
        print(step)
        break