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}) $ 으로 시간초과가 발생합니다.
많은 단계를 수행하는 경우 예제
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)