[백준] 20055번 컨베이어 벨트 위의 로봇 _ 문제 풀이

 


1. 문제

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

2. 풀이

삼성 SW 역량테스트 문제입니다. 삼성 문제에서 쉬운 편이라고 하지만 저는 시간초과로 많은 시간을 보냈습니다. 풀이 순서는 아래와 같습니다.

2.1. 시간초과 코드

이 문제를 풀때 자료구조는 리스트만 사용했고, 회전하는 경우에는 queue를 사용하는 것이 아니라 index만 하나씩 증가시켜서 시작점만 갱신해주는 방법을 사용했습니다. 로봇은 list에 들어있고, 들어온 순서대로 자신의 위치를 가지고 있습니다.

처음 푼 문제는 시간초과를 받았습니다. 아래와 같은 예제를 정답 소스코드에 넣어보면 199800 번의 round를 수행하게 됩니다. 이는 $ 200 \times 1000 $ 에 근사하는 수치로, $ O(2N \times 1000) $ 이라고 볼 수 있습니다. 각 라운드에 수행하는 시간복잡도를 위의 시간복잡도에 곱해주면 실제 시간 복잡도가 나오게 됩니다.

시간 초과 코드는 매번 로봇 N 개가 들어있는 list를 전부 탐색하는 메소드를 N번 호출하였습니다. 이 경우, 매번 $ O(N^2) $ 이 추가되어 $ O(2000 N^{3}) $ 으로 시간초과가 발생합니다.

image 많은 단계를 수행하는 경우 예제

100 200 
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 

위의 값은 시간이 많이 걸리는 경우의 값이고, 소스코드는 아래와 같습니다.

N, K = map(int, input().split())
A = list(map(int, input().split()))
maps = []
start_num = 0
robots = []

## 벨트가 한 칸 회전한다.
def rotate():
    global start_num
    start_num = (start_num - 1) % (2*N)

## 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
## 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
## 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
def robots_move():
    global robots
    for i in range(len(robots)):
        # 현재 로봇이 내려가는 위치에 있으면 내려감
        if robots[i] == (start_num + N - 1) % (2*N):
            robots[i] = -1
            continue

        next_robot = (robots[i] + 1) % (2*N)
        ## 다음 위치에 로봇 있는지 체크 & 내구도 체크후 못가면 다음 로봇
        if robots.count(next_robot) or A[next_robot] <= 0:
            continue

        # 이동 후 내구도 감소
        robots[i] = next_robot
        if robots[i] == (start_num + N - 1) % (2 * N):
            robots[i] = -1

        A[next_robot] -= 1

    robots = [x for x in robots if x != -1]

    if robots.count(start_num) == 0 and A[start_num] > 0:
        robots.append(start_num)
        A[start_num] -= 1

round = 1
while True:
    rotate()
    robots_move()
    ## 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
    if A.count(0) >= K:
        break
    round += 1
print(round)

2.2. 통과 코드

위의 소스코드에서 로봇을 찾는 시간을 줄이기 위하여 추가로 dictionary 를 사용해서 시간을 줄였습니다. 추가로 시간을 줄이기 위해서 각 단계에서 매번 A가 0인 것을 세지 않고, A가 0인 것이 발생했을 때, count 를 옮겨주는 전략을 사용했습니다.

N, K = map(int, input().split())
A = list(map(int, input().split()))
maps = []
start_num = 0
robots = []
robots_dict = {}
zeros = 0

## 벨트가 한 칸 회전한다.
def rotate():
    global start_num
    start_num = (start_num - 1) % (2 * N)

## 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
## 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
## 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
def robots_move():
    global robots, robots_dict, zeros
    for i in range(len(robots)):
        # 현재 로봇이 내려가는 위치에 있으면 내려감
        if robots[i] == (start_num + N - 1) % (2 * N):
            robots_dict.pop(robots[i])
            robots[i] = -1
            continue

        next_robot = (robots[i] + 1) % (2 * N)
        ## 다음 위치에 로봇 있는지 체크 & 내구도 체크후 못가면 다음 로봇
        if robots_dict.get(next_robot, False) or A[next_robot] <= 0:
            continue

        # 이동 후 내구도 감소
        robots_dict.pop(robots[i])
        robots[i] = next_robot
        robots_dict[next_robot] = True
        A[next_robot] -= 1
        if A[next_robot] == 0:
            zeros += 1

        # 현재 로봇이 내려가는 위치에 있으면 내려감
        if robots[i] == (start_num + N - 1) % (2 * N):
            robots_dict.pop(robots[i])
            robots[i] = -1

    robots = [x for x in robots if x != -1]

    if robots_dict.get(start_num, False) is False and A[start_num] > 0:
        robots.append(start_num)
        robots_dict[start_num] = True
        A[start_num] -= 1
        if A[start_num] == 0:
            zeros += 1

round = 1
while True:
    rotate()
    robots_move()
    ## 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
    if zeros >= K:
        break
    round += 1
print(round)

2.3. Deque 를 이용한 풀이

덱을 이용하면 하기와 같이 문제를 해결할 수 있습니다.

import sys
from collections import deque 
n,k = map(int,input().split())
arr = deque(list(map(int,input().split())))
zeros = 0
step = 1
robot = deque(list([0]*n))

while True:     
    # 1단계 벨트가 한 칸 회전한다.
    arr.rotate(1)
    robot.rotate(1)
    robot[-1] = 0
    
    # 2단계 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 
    # 만약 이동할 수 없다면 가만히 있는다.
    for i in range(-2, -n-1, -1):
        if robot[i] == 1 and robot[i+1] == 0 and arr[i+1-n] > 0:
            robot[i] = 0
            robot[i+1] = 1
            arr[i+1-n] -= 1
            if arr[i+1-n] == 0:
                zeros += 1
    robot[-1] = 0
    
    # 3단계 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
    if robot[0] == 0 and arr[0] > 0:
        robot[0] = 1 
        arr[0] -= 1
        if arr[0] == 0:
            zeros += 1
    
    # 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
    if zeros >= k:
        break
    step += 1
print(step)