백준 20055 컨베이어 벨트 위의 로봇 (파이썬)

문제

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

 

첫번째 풀이

최적화 이전 방법 (Python3는 시간초과, pypy3 는 통과) 

 

1. 한 칸 회전

• deque의 rotate를 이용하여 구현, robot을 벨트 위 index로 저장
• popleft를 사용하여 처음 넣은 로봇이 처음 이동하게 만듦 
• robot에 저장된 인덱스를 1씩 증가 시켜 벨트 N번 칸이 아닐 경우만 로봇을 저장

2. 모든 로봇 한 칸씩 이동

• popleft로 먼저 올라간 로봇 먼저
• 로봇의 위치를 저장한 robots 배열에서 현재 로봇이 다음 칸에 로봇이 있는지 확인 not in 으로 확인
• 처음 로봇이 N번째 위치에 있다면 robots 배열에 다시 삽입 X

3. 로봇 추가

4. count로 내구도 0인 벨트 개수 확인

5. 마지막에 0개수가 K보다 크거나 같다면 종료  

from collections import deque
N, K = map(int, input().split())
belt = deque(list(map(int, input().split())))
robots = deque([])
stage = 0
while True:
    stage += 1

    #벨트와 로봇 함께 회전
    belt.rotate(1)
    for _ in range(len(robots)):
        ri = robots.popleft()
        ri += 1
        if ri != N-1:
            robots.append(ri)
    empty = 0

    #로봇 한 칸 이동
    for _ in range(len(robots)):
        ri = robots.popleft()
        # 내구도가 0 이상, 앞에 로봇 없는 경우
        if belt[ri+1] > 0 and ri+1 not in robots:
            ri += 1
            belt[ri] -= 1
            # N번째 칸일때

        if ri != N - 1:
            robots.append(ri)

    #로봇 추가
    if belt[0] > 0:
        belt[0] -= 1
        robots.append(0)
    empty = belt.count(0)

    if empty >= K:
        print(stage)
        break

 

위 경우 문제는 통과하였지만 다소 불필요한 계산과 효율적이지 않은 코드라 아래와 같이 수정하여 두 번째 코드를 제출하였습니다.

 

두번째 풀이

최적화 이후 방법 (Python3, pypy3 모두 통과)

 

1. 한 칸 회전

• robots에 로봇들의 idx를 저장하지 않고 벨트와 같이 표현 있으면 1, 없으면 0
• popleft를 없애고 robots도 rotate로 회전 시키고 N번째는 0으로 수정

2. 모든 로봇 한 칸씩 이동

• popleft가 아닌 역순으로 N-1 번째 로봇부터 확인
• not in 말고 index로 확인 +1하여 앞에 로봇이 없는지 있는지
• 매 반복문 마다 벨트의 내구도가 0인지 확인

4. count를 사용하지 않고 바로 내구도 0인 경우 확인 

 

from collections import deque
N, K = map(int, input().split())
belt = deque(list(map(int, input().split())))
robots = deque([0] * N)
stage = 0
empty = 0

while True:
    stage += 1
    #벨트와 로봇 함께 회전
    belt.rotate(1)
    robots.rotate(1)
    robots[N-1] = 0

    #로봇 한 칸 이동
    for ri in range(N-2, -1, -1):
        if robots[ri] == 0:
            continue
        # 내구도가 0 이상, 앞에 로봇 없는 경우
        if belt[ri+1] > 0 and not robots[ri+1]:
            robots[ri] = 0
            ri += 1
            belt[ri] -= 1
            if belt[ri] == 0:
                empty += 1
        # N번째 칸이 아닐때만
        if ri != N - 1:
            robots[ri] = 1

    #로봇 추가
    if belt[0] > 0:
        belt[0] -= 1
        robots[0] = 1
        if belt[0] == 0:
            empty += 1

    if empty >= K:
        print(stage)
        break

제출 

후기

처음에 예제가 K = 2라서 empty >= 2를 넣고 구현을 해서 맞는 코드인데도 불구하고 틀렸다고 판단하여 시간을 뺏겼습니다. 이러한 잔 실수를 줄이고 꼼꼼히 코드를 구현하는 것이 중요한 것 같습니다.

그나마 최근에 풀었던 삼성 기출 중에서는 쉬운 편인 것 같아 수월하게 풀었던 것 같습니다