[Python][백준/BOJ] 20055번 : 컨베이어 벨트 위의 로봇

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

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

 

내 코드(List.ver)

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
belt =list(map(int, input().split()))
    
def solution(n, belt):
    step =1 #처음 수행은 1번째 단계
    robot = [False for _ in range(n)]
    while 1: #-1 로 하면 integer로 인식, int + list로 오류 뜨기 때문에 [-1:]로 처리해줘야 함
        belt = belt[-1:] + belt[:-1]
        robot = robot[-1:] + robot[:-1]
        
        if robot[n-1]:
            robot[n-1]=False
            
        for now in range(n-1,-1,-1): #매번 검사해야 하는 것들
            #뒤에서부터 검사함
            nxtidx = (now+1)%len(robot)
            
            if robot[now] and not robot[nxtidx] and belt[nxtidx] >0:
                robot[now] =False
                robot[nxtidx] =True
                belt[nxtidx] -=1
                if robot[n-1]:
                    robot[n-1] = False

        if belt[0] >0:
            belt[0] -= 1
            robot[0] =True
        
        total =0
        for p in belt:
            if p <1:
                total +=1
        if total >= k:
            break

        step+=1
    return step
            
print(solution(n, belt))

 

Deque.ver

import sys
input = sys.stdin.readline
from collections import deque

n, k = map(int, input().split())
belt =deque(list(map(int, input().split())))
robot = deque([0 for _ in range(n)])

step =0
while belt.count(0) < k:
    belt.rotate(1)
    robot.rotate(1)
    robot[-1] = 0 #내리는 위치
    if sum(robot) >0:
        for now in range(n-1, -1, -1): #이미 -1은 검사했으니까
            nxtidx = (now+1)%n
            if robot[now] and robot[nxtidx] == 0 and belt[nxtidx] >0:
                robot[now] = 0
                robot[nxtidx] =1
                belt[nxtidx] -=1
            robot[-1] =0
    if belt[0] >0:
        robot[0] =1
        belt[0] -=1
    step +=1
    
print(step)

 

코드 리뷰

구현

삼성이 상어 시리즈 말고 로봇 시리즈도 미는 것 같다...저번 로봇 청소기에 이어 두 번째 로봇 시리즈다. 이번 로봇도 마찬가지로 자기 알아서 척척 잘 움직이기 때문에 코드를 복잡하게 만든다. (분노..-.-) 하지만 조건대로 코드를 나열하면 풀리는 경향이 있어 화가 조금 덜 난다.

문제 조건...너무 길다

처음에는 이 문제를 풀 때 deque으로 풀고 deque.rotate를 이용하려고 했다. 내가 생각한 deque은 튜플 형태로 필요한 모든 조건의 값들을 받아서 계산하고, while q로 계속해서 갱신하며 돌리는 것이었다. 하지만 이렇게 풀게 되면 너무 복잡했다.

 

그리고 robot이랑 belt 는 따로 움직이기 때문에 따로 배열을 만들어서 계산해주는 것이 편했다. 이것만 지킨다면 queue든 list든 상관 없이 잘 풀릴 것 같다. 조만간 deque으로 다시 풀어볼 예정이다. 그러면 코드를 뜯어보자.

 

def solution()

def solution(n, belt):
    step =1 #처음 수행은 1번째 단계
    robot = [False for _ in range(n)]
    while 1: #-1 로 하면 integer로 인식, int + list로 오류 뜨기 때문에 [-1:]로 처리해줘야 함
        belt = belt[-1:] + belt[:-1]
        robot = robot[-1:] + robot[:-1]
        
        if robot[n-1]:
            robot[n-1]=False

이건 회전시키는 방법이다. belt 안에는 각각의 칸에 대한 내구도가 있고, robot은 처음에는 존재하지 않기 때문에 False로 초기화되어 저장되어 있다. 컨테이너 벨트처럼 그대로 움직이는 코드이다. 그리고 중요한 점은 belt[-1] + belt[:-1]를 하게 되면 belt[-1]을 integer로 취급하기 때문에 오류가 발생한다. 그래서 리스트끼리 더할 때는 값이 하나더라도 무조건 리스트 형태로 만들어서 연산해야 한다.

 

그리고 '내리는 위치'에 로봇이 있다면, 자동으로 로봇이 내려가기 때문에 False로 존재 여부를 재설정해준다.

for now in range(n-1,-1,-1): #매번 검사해야 하는 것들
            #뒤에서부터 검사함
            nxtidx = (now+1)%len(robot)
            
            if robot[now] and not robot[nxtidx] and belt[nxtidx] >0:
                robot[now] =False
                robot[nxtidx] =True
                belt[nxtidx] -=1
                if robot[n-1]:
                    robot[n-1] = False

이건 컨테이너가 한 칸 움직일 때마다 벨트를 한 칸씩 검사하기 위해서 만든 반복문이다. 뒤에서부터 확인을 해주어야 하기 때문에 n-1으로 돌린다. (2n-1으로 반복문을 설정하면 시간 초과가 나기 때문에 주의하자!) nxtidx는 다음 칸을 의미한다. 2n+1이 될 경우 다시 1로 넘어가야 하기 때문에 %를 사용하여 계속해서 무한 회전할 수 있도록 만들었다.

 

칸을 확인할 때, 1. 로봇이 현재 위치에 있고, 2. 로봇이 다음 위치에 없고, 3. 다음 칸의 내구도가 0 보다 큰 수라면 조건에 딱 들어맞기 때문에 로봇을 한 칸 옮겨야 한다. 그래서 현재 위치를 비워주고, 다음 칸을 채워주고 내구도를 1 깎으면 된다. (진짜 구현 그대로다...) 이 때에도 잊지 말아야 할 것은 만약 '내리는 위치'에 로봇이 존재한다면 로봇 내려줘야 한다.

 

        if belt[0] >0:
            belt[0] -= 1
            robot[0] =True
        
        total =0
        for p in belt:
            if p <1:
                total +=1
        if total >= k:
            break

        step+=1
    return step

그리고 '올리는 위치'를 확인하는데, 올리는 위치가 0보다 커야 올릴 수 있으니까, 0보다 큰지 확인한다. 그리고 크면 내구도 1 깎고, True를 통해 로봇을 올린다.

 

이후 for문이 한 바퀴 다 돌았으면, 내구도가 0인 칸이 몇 개인지, k개 이상인지 확인해야 하니까 확인하고, 이상이면 break 걸어서 빠져나간다. 그리고 문제에서 요구하는 'step'을 1씩 카운팅해준다.

 

이 문제는 진짜 구현만을 요구하는 문제이다. 조건에 써진 대로 풀면 풀리는 문제이다. deque으로 다시 한 번 풀어봐야겠다.