[BOJ] 20055번 컨베이어 벨트 위의 로봇 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

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

풀이

문제를 이해하는데 시간을 많이 썼다. 단계별로 필요한 부분을 손코딩으로 하고 들어가서 편했다. deque을 이용해서 풀이했는데, 코드 적을때 appendleft를 append로 잘못 적은 부분이 존재해서 테스트 케이스가 틀렸어서 이런 부분까지 확실히 이해하면서 집중해서 코드를 작성해야겠다는 생각을 했다.

추가로 시간복잡도를 확실하게 계산하지 못하고 우선 제출한 감이 있어서 시간복잡도 구하는 연습을 더 할 필요를 느꼈다.

deque에서 pop하고 appendleft하는걸 rotate 메소드를 이용해서 대체가능하다.

from collections import deque

N, K = map(int, input().split())
durabilites = deque(list(map(int, input().split())))
robots = deque([]) # durabilities의 인덱스를 저장(0~2N-1), 항상 오름차순된다!

step = 1
while True:
    # 1. 벨트가 로봇과 함께 회전
    durabilites.appendleft(durabilites.pop())
    robots = [robot+1 for robot in robots if (robot+1) !=(N-1)] # 내리는 위치에 도달한 로봇 제거
        

    # 2. 로봇 이동(이때도 내리는 위치 도달하면 내린다)
    new_robots=deque([])
    for robot in reversed(robots):
        if (robot+1) not in new_robots and durabilites[robot+1] >= 1:
            durabilites[robot+1] -= 1 # 로봇 이동했으니 내구도 감소
            if robot+1 == N-1: # 내리는 칸이면 내리기
                continue
            else:
                new_robots.appendleft(robot+1) # 한칸 이동
        else:
            new_robots.appendleft(robot) # 이동X
    robots = new_robots

    # 3. 올리는 위치에 로봇 올리기
    if durabilites[0] > 0:
        robots.appendleft(0)
        durabilites[0] -= 1


    # 4. durabilities에서 0이 k개 이상이면 과정 종료
    if durabilites.count(0) >= K: # 시간복잡도 최적화 필요
        break

    step += 1 # step 1 증가


print(step)