deque도 인덱스로 접근해서 원소 수정이 가능하다 -컨베이어 벨트 위의 로봇-

1. 문제

 

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

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

 

컨베이어 벨트 위에 로봇을 올릴때, 로봇이 움직이면서 칸의 내구도가 점차 감소한다

 

몇단계가 지나야 컨베이어 벨트 작동이 멈추는지 구해보자

 

 

2. 풀이

 

문제를 먼저 잘 이해해야겠다

 

1번부터 2n번까지 있는데 1번이 "올리는 위치"이고 n번이 "내리는 위치"라고 한다

 

 

그러면서 마치 2n번으로 오면 1번으로 올라오고 n번으로 가면 n+1번으로 내려가는 듯한 인상을 주는데..

 

"길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다."

 

이거 보니까 위쪽에 길이 n인 컨베이어벨트고 아래에 n인 예비?벨트가 감싸면서 올라오는 형태인가로 깨달음

 

 

 

그러면 모든 준비가 끝났다

 

회전을 해야하니까 deque를 사용하는게 적절한것 같다

 

로봇은 1부터 n인 곳에만 움직일 수 있다고 하니까 길이 n인 deque를 만든다

 

from collections import deque
from sys import stdin

n,k = map(int,stdin.readline().split())

belt = deque(map(int,stdin.readline().split()))

#로봇은 1~n인 곳에만 움직인다
robot = [0]*n

robot = deque(robot)

 

 

벨트가 완성되었으니까 시뮬레이션을 수행함

 

제시되는 순서에 따라 시뮬레이션을 수행해야함

 

 

 

벨트가 각 칸 위에 있는 로봇과 함께 한칸 회전한다가 먼저인데..

 

로봇이 없으니까 로봇부터 올리면 잘못되었다는거임

 

로봇을 올리는건 보면 세번째 일인데

 

아무튼 deque를 썼으니까 rotate()를 이용해서 한칸 회전시키는것은 매우 쉽다

 

#시뮬레이션 수행

stage = 1

while 1:
    
    #벨트를 회전시키면서 로봇도 회전시킴

    belt.rotate(1)
    robot.rotate(1)

 

여기서 하나를 놓치고 넘어가기 쉬운데

 

처음에는 로봇이 없으니까 아무 생각을 못하기 쉽지만 여러 단계 진행하다보면 로봇이 있는 상태이고

 

한칸 회전하면 로봇이 n-1번째 칸에 있을 수 있고

 

그러면 로봇은 즉시 내려야한다

 

    if robot[n-1] == 1: ##로봇이 n-1번으로 이동해버리면
        
        robot[n-1] = 0 #로봇을 내린다

 

다음에 벨트가 움직이는데 로봇이 이동한다는건 도대체 무슨일이야? 라고 생각하기 쉬웠는데

 

"로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다. "라고 적혀있어

 

로봇 리스트를 순회해서 로봇이 i번째 칸에 존재한다면...

 

i+1번째 칸에는 로봇이 존재하는지, i+1번째 칸의 내구도가 1이상인지를 검사한다

 

------------------------------------------------------------------------------------------------------------------------

 

그리고 여기서 내가 deque는 인덱스 접근이 안되는줄 알았는데(옛날에 안된것 같았는데..?)

 

deque가 인덱스 접근이 가능하더라고??? 

 

그리고 인덱스 접근해서 원소 변경도 가능하고

 

 

---------------------------------------------------------------------------------------------------------------------------

 

 

그렇다면 로봇을 실제로 i+1번째 칸으로 옮기고

 

i번째 칸의 로봇은 0으로 바꿔준다

 

그리고 이동했으면 i+1번째 칸의 내구도를 1 감소시킨다

 

    #로봇을 순회해서 이동할 수 있는지 검사하고 로봇을 이동
    #0번째 칸과 n-1번째 칸에는 존재할리 없으니 빼고 검사

    for i in range(n-2,0,-1):
        
        #i번째 칸에 로봇이 존재한다면...
        if robot[i] == 1:
            
            if robot[i+1] == 0 and belt[i+1] >= 1: #다음 칸에 로봇이 존재하지 않고, 내구도가 1 이상
                
                robot[i+1] = robot[i] #i번째 로봇을 옮겨주고
                robot[i] = 0 #i번째 위치는 0으로 만들고
                belt[i+1] -= 1 #이동하면 내구도 1을 감소시킨다

 

그런데 여기서 조금 디테일이 필요한데 만약에 습관처럼 0번부터 n-1번으로 순방향 순회를 한다면?

 

i번째 칸에 로봇이 존재하는지 검사하고..

 

그러면 i+1번째 칸에 로봇이 존재하는지 검사하고, i+1번째 칸에 내구도가 1인지 아닌지

 

검사하고 이게 잘 맞았어..

 

그러면 i+1번째로 옮기겠지??

 

그런데 순방향으로 순회하니까 다음에는 i+1번째를 검사하겠네??

 

근데 이미 i+1번째의 로봇은 i번째 로봇에서 옮겨온건데 또 이동시킬거야??

 

그러면 이걸 방지하기 위해 배열 하나를 더 써??

 

그러지말고..

 

역방향으로 순회한다면 어떨까??

 

n-2번부터 0번까지 역방향으로 순회한다면... n-2번은 n-1번으로 옮기고

 

n-3번은 n-2번으로 옮기고

 

n-4번은 n-3번으로 옮기고....

 

그러면 위와같이 중복해서 옮기는 문제는 없어진다

 

--------------------------------------------------------------------------------------------------------------

 

아무튼 로봇을 이동시키고 나면, 이제 n-1번 내리는 위치에 로봇이 올수 있지

 

그런 경우 로봇을 즉시 내린다

 

        #내리는 위치로 로봇이 이동하면 즉시 내린다.

        if robot[n-1] == 1:
            
            robot[n-1] = 0

 

 

다음 3단계가 올리는 위치의 내구도가 0인지 아닌지 검사하고, 0이 아니라면 로봇을 올린다

 

로봇을 올리면 내구도를 1 감소시키라 했으니까 내구도 1 감소시키는것도 까먹지말고

 

    #올리는 위치에 로봇이 존재하지 않으면..
    if robot[0] == 0:
        
        #올리는 위치의 내구도가 0이 아니라면, 
        if belt[0] != 0:
            
            #로봇을 올리고
            robot[0] = 1

            belt[0] -= 1 #내구도를 1 감소함

 

 

다음 마지막은 내구도가 0인 칸의 개수가 k개 이상이면 과정을 종료시키라고 했어

 

그러니까 belt를 순회해서 내구도가 0인 칸의 개수가 몇개인지 세야해

 

    #내구도가 0인 칸이 몇개인지 검사

    zero = 0

    end = False

    for d in belt:
        
        if d == 0:
            
            zero += 1
        
        #내구도가 0인 칸이 k개 이상이면 종료
        if zero >= k:
            
            end = True
            break

 

 

여기서도 효율 따질려고? 매 과정에서 내구도가 1씩 감소할때마다, 내구도가 0인지 아닌지 검사하고, 내구도가 0인 칸의 개수를 따로 저장해서 

 

순회하는 과정을 없애볼려고 했는데

 

애초에 시뮬레이션 단계가 중간에 내구도가 0인 칸의 개수가 k개 이상이면 즉시 종료하라는게 아니라

 

마지막 단계에서 내구도가 0인 칸의 개수가 k개 이상이면 과정을 종료하라고 했거든

 

그러니까 중간에 내구도가 0인 칸의 개수를 계속해서 세는건 잘못된거야??

 

아니 근데 어떻게 잘하면 할수도 있을것 같긴하네

 

from collections import deque
from sys import stdin

n,k = map(int,stdin.readline().split())

belt = deque(map(int,stdin.readline().split()))

#로봇은 1~n인 곳에만 움직인다
robot = [0]*n

robot = deque(robot)

#시뮬레이션 수행

stage = 1

while 1:
    
    #벨트를 회전시키면서 로봇도 회전시킴

    belt.rotate(1)
    robot.rotate(1)

    if robot[n-1] == 1: ##로봇이 n-1번으로 이동해버리면
        
        robot[n-1] = 0 #로봇을 내린다

    #로봇을 순회해서 이동할 수 있는지 검사하고 로봇을 이동
    #0번째 칸과 n-1번째 칸에는 존재할리 없으니 빼고 검사

    for i in range(n-2,0,-1):
        
        #i번째 칸에 로봇이 존재한다면...
        if robot[i] == 1:
            
            if robot[i+1] == 0 and belt[i+1] >= 1: #다음 칸에 로봇이 존재하지 않고, 내구도가 1 이상
                
                robot[i+1] = robot[i] #i번째 로봇을 옮겨주고
                robot[i] = 0 #i번째 위치는 0으로 만들고
                belt[i+1] -= 1 #이동하면 내구도 1을 감소시킨다
        
        #내리는 위치로 로봇이 이동하면 즉시 내린다.

        if robot[n-1] == 1:
            
            robot[n-1] = 0
    
    #올리는 위치에 로봇이 존재하지 않으면..
    if robot[0] == 0:
        
        #올리는 위치의 내구도가 0이 아니라면, 
        if belt[0] != 0:
            
            #로봇을 올리고
            robot[0] = 1

            belt[0] -= 1 #내구도를 1 감소함
    
    #내구도가 0인 칸이 몇개인지 검사

    zero = 0

    end = False

    for d in belt:
        
        if d == 0:
            
            zero += 1
        
        #내구도가 0인 칸이 k개 이상이면 종료
        if zero >= k:
            
            end = True
            break
    

    if end == True:
        
        break
    
    else:
        
        stage += 1 #종료하지 않으면 stage를 1 증가


print(stage)

 

 

아무튼 과정이 종료됐다면, 반복문을 탈출하고 stage를 출력

 

과정이 종료된게 아니라면 stage를 1 증가시키고 다음 반복문을 수행

 

 

3. 되돌아보기

 

시뮬레이션의 기본은 항상 문제에서 제시하는 순서대로 그대로 성실하게 구현

 

처음에 로봇 벨트 회전하고나서, n-1번째 칸에 로봇이 올수도 있으며, 즉시 내려야한다는점을 생각하기 어려웠고

 

deque에 인덱스로 접근해서 값을 수정할 수 있다는점

 

로봇을 i번째 칸에서 i+1번째 칸으로 옮길때, 순방향으로 순회하면 중복을 고려해야하는 문제가 생기니까

 

역방향으로 순회해서 중복을 고려하지 않도록 하는 디테일