BOJ G5 20055 컨베이어 벨트 위의 로봇 JAVA

 

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

 

문제를 한 번 읽고 자료구조를 뭘 쓰면 좋을 지 고민했다. 컨베이어 벨트는 고정된 2N 길이이기 때문에 배열에 담고, 벨트가 회전하는 것은 직접적으로 계속 배열의 값을 돌리는 게 아니라 컨베이어 벨트의 시작 인덱스와 끝 인덱스를 담아놓고 조작하는 방식이 더 효율적일 것이라 생각했다.

그리고 로봇의 경우에는 제한 없이, 종료 조건을 만족하기 전까지는 무한정으로 추가가 가능하기 때문에 Queue를 쓸까 하다가, 회전(이동)하는 동작(수정), 추가, 삭제하는 동작을 구현하려면 인덱스가 필요할 거라 판단해서 ArrayList를 이용했다.

---

문제 구현

<aside> 💡 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.

</aside>

컨베이어 벨트의 시작 인덱스(upIdx), 끝 인덱스(downIdx)를 1만큼 감소시킨다. 시작 인덱스란 올라가는 곳의 인덱스이고, 끝 인덱스란 내려가는 곳의 인덱스를 말한다.

위 단계에는 벨트와 로봇이 함께 한 칸 회전한다고 되어있기 때문에 헷갈릴 수 있지만, 벨트의 인덱스만 조정해주면 로봇은 자동으로 이동된다.

!! 이동 후 downIdx에 도달한 로봇은 삭제한다

<aside> 💡 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.

</aside>

robot을 처음부터 순회하면서 동작을 수행한다.

여기서 preIdx를 사용해서 앞선 로봇의 위치에 다음 로봇이 겹치지 않도록 해주었다.

!! 이동 후 downIdx에 도달한 로봇은 삭제한다

<aside> 💡 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.

</aside>

<aside> 💡 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

</aside>

나머지는 그대로 구현하면 된다.

---

실수한 부분

연산자 우선순위

벨트가 회전하는 부분에서 인덱스 조작을 이용했다.

upIdx = ((upIdx-1)+(2*N)) % 2*N;    (X)
upIdx = ((upIdx-1)+(2*N)) % (2*N);  (O)

처음에 위 방식으로 했었는데 답이 나오지 않았다. 연산자 우선순위를 제대로 몰라서 혹시 몰라 아래 방법으로 했더니 답이 나왔다.

*보다 %연산이 우선적으로 적용된다는 걸 다시 한 번 알 수 있었다.

ArrayList의 변경 연산자

set(index, val)

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_G5_20055_컨베이어벨트위의로봇 {

    static int[] line;
    static int N, K;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        line = new int[2*N];
        st = new StringTokenizer(in.readLine());
        for (int i = 0; i < 2*N; i++){
            line[i] = Integer.parseInt(st.nextToken());
        }

        int upIdx = 0; //시작 idx
        int downIdx = N-1;
        List<Integer> robot = new ArrayList<>();
        int zeroCnt = 0; //내구도 0인 것의 개수
        int cnt = 0;
        while(zeroCnt < K){
            cnt++;
            //1. 회전 : 인덱스 변환. 로봇과 함께 회전
            upIdx = ((upIdx-1)+(2*N)) % (2*N);
            downIdx = ((downIdx-1)+(2*N)) % (2*N);

            //로봇이 끝에 도달하면.. 제거됨 : 연속적으로 제거해야 하므로 반대로 순회
            for (int i = robot.size()-1; i >= 0; i--){
                if (robot.get(i) == downIdx){
                    robot.remove(i);
                }
            }

            //2. 로봇만 한 칸 앞으로 이동 or 정지
            int preIdx = -2;
            for (int i = 0; i < robot.size(); i++){
                int curIdx = robot.get(i); //현재 로봇 위치
                int nextIdx = ((curIdx+1) % (2*N)); //한칸 이동 위치
                if (line[nextIdx] > 0 && preIdx != nextIdx){
                    //이동 가능하면 이동 + 내구도 감소
                    robot.set(i, nextIdx);
                    curIdx = nextIdx;
                    line[nextIdx]--;
                    if (line[nextIdx] == 0) zeroCnt++;
                }
                preIdx = curIdx;
            }
            //로봇이 끝에 도달하면.. 제거됨 : 연속적으로 제거해야 하므로 반대로 순회
            for (int i = robot.size()-1; i >= 0; i--){
                if (robot.get(i) == downIdx){
                    robot.remove(i);
                }
            }

            //3. 로봇을 올리는 위치에 하나 추가
            if (line[upIdx] > 0){
                robot.add(upIdx);
                line[upIdx]--;
                if (line[upIdx] == 0) zeroCnt++;
            }
        }
        System.out.println(cnt);

    }

}