문제
https://www.acmicpc.net/problem/20055
풀이
answer = 1
n,k = map(int,input().split())
arr = list(map(int,input().split()))
robot = [0] * (2*n)
order = []
def output_robot():
## 로봇 내리기
if robot[n - 1] == 1:
robot[n - 1] = 0
def rotate():
arr_end = arr[-1]
robot_end = robot[-1]
for i in range(2*n-1,0,-1 ):
arr[i] = arr[i-1]
robot[i] = robot[i-1]
arr[0] = arr_end
robot[0] = robot_end
## 로봇 내리기
output_robot()
def move_robot():
for i in range(n-1,0,-1):
if robot[i-1] == 1 and robot[i] == 0 and arr[i] >=1 :
robot[i] = robot[i-1]
robot[i-1] = 0
arr[i] -= 1
## 로봇 내리기
output_robot()
def input_robot():
if robot[0] == 0 and arr[0] >= 1:
robot[0] = 1
arr[0] -= 1
def end_check():
cnt = 0
for i in range(2*n):
if arr[i] == 0 :
cnt += 1
if cnt >=k:
return True
return False
while(1):
rotate()
move_robot()
input_robot()
if end_check() :
print(answer)
break
answer += 1
주의점
가장 오래된 로봇부터 = N칸 N-1, N-2, ... 1 순서대로이다.
N+1칸 ~ 2N칸 까지는 로봇이 존재하지 않는다. (N칸에서 빠지므로 새로 충원 전까지는 비어있음)
전체 컨베이어벨트 rotate와 로봇의 이동시 각각 N칸에 있는 로봇을 내려줘야한다.
deque rotate() 함수
deque에는 rotate 함수가 존재한다.
rotate(1) : 오른쪽으로 1칸씩 밀어줌
rotate(-2): 왼쪽으로 2칸씩 밀어줌
이런식이다.
코드 개선
rotate() 하는부분
개선전
arr_end = arr[-1]
robot_end = robot[-1]
for i in range(2*n-1,0,-1 ):
arr[i] = arr[i-1]
robot[i] = robot[i-1]
arr[0] = arr_end
robot[0] = robot_end개선후
arr.rotate(1)
robot.rotate(1)list가 아닌 deque로 선언하고 rotate() 함수로 간단하게 바꾸었다.
직접 짜줄 필요가 없다. 파이썬 갓
end check
내구성 0인것 k개 이상인지 체크하는 부분
개선전
cnt = 0
for i in range(2*n):
if arr[i] == 0 :
cnt += 1
if cnt >=k:
return True
return False개선후
return True if arr.count(0) >=k else False카운트역시 직접 짤 필요없이 이미 내장함수로 지원된다.
deque나 list나 둘다 제공한다.
.count('?') 로 카운트하면 간단하다.
최적화
근데 내구성 0인개수 체크하는부분은 count로 체크하는거보다 k개 이상이면 중단하고 return 처리하는게 더 빠르다. 테스트케이스가 커지면 특히 이부분은 효율성이 차이가 날것같다.
속도 역시 deque.rotate()를 사용하면 오히려 느리게 측정된다.
rotate함수도 시간복잡도 o(n)으로 구현되어있기는 하지만 그냥 list로 만들고 직접 돌리는게 더 빠른가보다.
서버 측정차이인가 싶어서 한 10번넘게 이것저것 바꿔가면서 돌려봤는데 rorate 함수 안쓰는게 훨씬 빠르다.
그래도 구현상 시간복잡도는 동일하고 코테볼때는 코드를 빠르게 짜는게 중요하므로 rotate 쓰면 편할거같다.
끝!
