[백준][구현] 컨베이어 벨트 위의 로봇

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

20055번: 컨베이어 벨트 위의 로봇

 

내가 작성한 코드

from collections import deque, defaultdict

def read_data():
    N, K = map(int, input().rstrip().split())
    A = list(map(int, input().rstrip().split()))
    upper = deque(A[:N])
    lower = deque(reversed(A[N:2*N]))
    z = A.count(0)

    return N, K, upper, lower, z

def rotate(upper, lower, N, robot, visited):
    lower.append(upper.pop())
    upper.appendleft(lower.popleft())
    for _ in range(len(robot)):
        x = robot.popleft()
        visited[x] = False
        if x+1 < N-1:
            robot.append(x+1)
            visited[x+1] = True

def move(upper, N, z, robot, visited):
    for _ in range(len(robot)):
        i = robot.popleft()
        if i+1 < N and not visited[i+1] and upper[i + 1] >= 1:
            visited[i] = False
            upper[i + 1] -= 1
            if upper[i + 1] == 0:
                z += 1
            if i+1 != N-1:
                robot.append(i+1)
                visited[i + 1] = True
        else:
            robot.append(i)
    return z

def add_robot(upper, robot, z, visited):
    if upper[0] > 0 and (not robot or robot[-1] != 0):
        robot.append(0)
        visited[0] = True
        upper[0] -= 1
        if upper[0] == 0:
            z += 1
    return z

def get_answer(N, K, upper, lower, z):
    robot = deque()
    visited = defaultdict(bool)
    phase = 0

    while z < K:
        rotate(upper, lower, N, robot, visited)
        z = move(upper, N, z, robot, visited)
        z = add_robot(upper, robot, z, visited)
        phase += 1
        # debug(robot, upper, z, phase)

    return phase

def debug(robot, upper, z, phase):
    print(f"=========={phase}==========")
    print(f"upper : {upper}")
    print(f"robot : {list(robot)}")
    print(f"z : {z}")

def test():
    N, K = 100, 200
    A = [1000, 0] * (1 * N)
    upper = deque(A[:N])
    lower = deque(reversed(A[N:2 * N]))
    z = A.count(0)

    # N, K = 5, 1
    # A = [2] * (2 * N)
    # upper = deque(A[:N])
    # lower = deque(reversed(A[N:2 * N]))
    # z = A.count(0)

    return N, K, upper, lower, z

N, K, upper, lower, z = read_data()
# N, K, upper, lower, z = test()
print(get_answer(N, K, upper, lower, z))

• 로봇의 위치 구조체
  
  • 처음에 defaultdict로 구현하여 keys()로 접근
    - 움직일 위치의 로봇이 있는지 확인할 때 접근하여 key에 추가됨
  • deque로 바꾸어 for문을 len만큼 돌리고 pop/push
• 로봇의 위치 확인
  • 로봇이 움직일 위치에 로봇이 존재하는지 확인이 필요
  • deque로 바꿨으므로 in으로 확인함
    - i+1 in robot
    - 시간초과
  • bisect로 구현
    - robot은 항상 정렬되어있으므로 bisect로 구현
    - N이 최대 100이므로, bisect로 시간이 크게 줄지 않음
    - 시간초과
  • 로봇의 위치를 defautdict로 변경

 

다른 사람이 작성한 코드

None

• 강한 구현문제로 다른 코드를 참고하지 않음

 

기억해야할 것

• 성능 고려
  
  • 엣지케이스를 조사할 때 최악의 시간으로 체크하지 못함
    - N, K = 100, 200이고, A = [1000] * (2 * N)
    - 이 경우 로봇이 한 단계에서 2번 올라오므로, 더 빠른 속도로 감소
    - A = [1000, 0] * N으로 변경하니 시간이 오래걸림을 확인
  • N = 100이라 "in"으로 해결될 줄 알았음
    - 최악의 경우, phase가 200,000번으로 성능 감소의 요인이 된 듯