백준 20055

🤖 백준 20055 : 컨베이어 벨트 위의 로봇

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

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

🤖 쉬웠는데, 딱 한 조건 빼먹어서 고생한 문제...부들부들... 

🤖 나는 컨베이어벨트가 두 줄이고, 첫 줄의 마지막 원소를 두 번째 줄의 마지막에, 두 번째 줄의 첫 원소를 첫 줄의 맨 앞에 넣는 것을 보고 LinkedList를 사용하면 되겠다고 생각했다. 

🤖 그리고 문제 조건에서 보면 알겠지만, 결국 로봇은 첫 줄에서만 움직인다. 그래서 로봇은 크기가 n인 배열로 만들었다. 

🤖 그리고, 문제 읽어보면 당연히 로봇 먼저 올리고 컨베이어 벨트 회전하는건줄 알았는데, 그게 아니라고 한다... 문제가 약간 말을 꼬아놓은 느낌이 있다.

🤖 과정  (while 문안에서 이대로 수행, while 조건은 내구도 0인 칸의 개수가 k보다 작다면) 

• 컨베이어 벨트 회전(회전에 의해 로봇도 한칸씩 이동, 이때는 내구도 그대로)
• 움직일 수 있는 로봇 움직임(움직일 경우 내구도 감소)
• 로봇 올림 

🤖 자료구조들

private static LinkedList<Integer> first;
private static LinkedList<Integer> second;
private static int[] robots;
private static int n, k, robotCount;

• robots를 굳이 Int로 안해도 된다. boolean으로 해도 상관없다. 
• 로봇 번호를 굳이 카운트할 필요 없는데, 처음에 있다고 생각해서 int[] robots, robotCount 변수를 만들어뒀었다.
• boolean[] robots, int n, k 이렇게 있으면 될듯
• first, second는 각 칸 내구도가 들어간다고 생각하면 된다! 

 

🤖 문제로직 

while (zeroCount() < k) {
    rotateBelt();
    robotSelfMove();
    onRobot();
    step++;
}

🤖 rotateBelt() : 컨테이너 벨트 회전 

static void rotateBelt() {
    int secondFirst = second.removeFirst();
    int firstLast = first.removeLast();

    first.addFirst(secondFirst);
    second.addLast(firstLast);

    // 첫 줄 마지막 칸 도착한 로봇은 내림
    for (int i = n-2; i >=0; i--) {
        robots[i+1] = robots[i];
    }
    robots[n-1] = 0;
    robots[0] = 0; // 이걸 빼먹어서 틀림
}

🤖 주의점!! 

• 먼저 컨베이어 벨트에 올라간 로봇이 먼저 내리므로, n-2부터 역순 탐색을 수행해야 한다. (질문게시판에 이 질문 많았다)
• 그리고 다 한칸씩 자동으로 땡겨지는 거니까 맨 첫 칸은 0으로(로봇 없는걸로) 만들어줘야 한다! 이걸 빼먹어서 답이 자꾸 이상하게 나왔다;;

 

 

🤖 robotSelfMove() : 움직일 수 있는 로봇은 한 칸씩 걷기

static void robotSelfMove() {
    for (int i = n-2; i >= 0; i--) {
        if (robots[i] > 0) { // 로봇이 있는 칸
            if (robots[i+1] == 0 && first.get(i+1) >= 1) {
                robots[i+1] = robots[i];
                robots[i] = 0;
                int st = first.get(i+1);
                first.set(i+1, st - 1);
            }
        }
    }
    robots[n-1] = 0;
}

• 로봇이 있는 칸인 경우, 다음칸에 로봇이 없고, 내구도가 1 이상인지 확인한다. 
  • 이 조건에 부합하면 옮겨주고, 원래 자리는 0으로 만든다.
  • 그리고 옮긴 후의 자리의 내구도는 -1해준다.
  • 마지막 칸에 도착한 로봇은 자동으로 내려준다(robots[n-1] = 0)

 

🤖 onRobot() 

static void onRobot() {
    int strength = first.get(0);
    if (strength > 0) {
        robots[0] = robotCount;
        first.set(0, strength-1);
    }

}

• 첫 번째 칸 내구도가 0보다 크면 올려주기 

 

 

🤖 zeroCount() 

static int zeroCount() {
    int count = 0;
    count += (int) (first.stream().filter(o -> o== 0).count());
    count += (int) (second.stream().filter(o-> o == 0).count());
    return count;
}

• first, second 각 리스트 돌면서 0인 칸의 개수를 세고 리턴. 

 

---

 

🤖 전체코드

import java.util.*;
import java.io.*;
public class p20055 {
    private static LinkedList<Integer> first;
    private static LinkedList<Integer> second;
    private static int[] robots;
    private static int n, k, robotCount;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        robotCount = 1;
        int step = 0;

        first = new LinkedList<>();
        second = new LinkedList<>();
        robots = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            first.add(Integer.parseInt(st.nextToken()));
        }

        for (int i = n; i < 2*n; i++) {
            second.addFirst(Integer.parseInt(st.nextToken()));
        }


        while (zeroCount() < k) {
            rotateBelt();
            robotSelfMove();
            onRobot();
            step++;
        }
        System.out.println(step);
    }



    static void onRobot() {
        int strength = first.get(0);
        if (strength > 0) {
            robots[0] = robotCount;
            first.set(0, strength-1);
        }

    }

    static void rotateBelt() {
        int secondFirst = second.removeFirst();
        int firstLast = first.removeLast();

        first.addFirst(secondFirst);
        second.addLast(firstLast);

        // 첫 줄 마지막 칸 도착한 로봇은 내림
        for (int i = n-2; i >=0; i--) {
            robots[i+1] = robots[i];
        }
        robots[n-1] = 0;
        robots[0] = 0; // 이걸 빼먹어서 틀림
    }

    static void robotSelfMove() {
        for (int i = n-2; i >= 0; i--) {
            if (robots[i] > 0) { // 로봇이 있는 칸
                if (robots[i+1] == 0 && first.get(i+1) >= 1) {
                    robots[i+1] = robots[i];
                    robots[i] = 0;
                    int st = first.get(i+1);
                    first.set(i+1, st - 1);
                }
            }
        }
        robots[n-1] = 0;
    }

    static int zeroCount() {
        int count = 0;
        count += (int) (first.stream().filter(o -> o== 0).count());
        count += (int) (second.stream().filter(o-> o == 0).count());
        return count;
    }

}