[BOJ - JAVA] 20055 - 컨베이어 벨트 위의 로봇 (시뮬레이션)

# 주소

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

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

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Robot{
    int x;
    int is;
    Robot(int x, int is){
        this.x = x;
        this.is = is;
    }
}
class Ma{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        ArrayList<Robot> list = new ArrayList<>();
        for(int i = 0; i < n * 2; i++)
            list.add(new Robot(scan.nextInt(), 0));
        int up = 0;
        int down = n - 1;
        int step = 1;
        while(true){
            //1단계
            Robot now = list.get(list.size() - 1);
            list.add(0, now);
            list.remove(list.size() - 1);
            if(list.get(down).is == 1)
                list.get(down).is = 0;
            //2단계
            Robot zero = list.get(0);
            if(zero.is == 0 && zero.x >= 1 && list.get(list.size() - 1).is == 1) {
                zero.is = 1;
                zero.x--;
                list.get(list.size() - 1).is = 0;
            }
            for(int i = list.size() - 2; i >= 0; i--){
                Robot real = list.get(i + 1);
                //현재 로봇이 없으면
                if(real.is == 0 && real.x >= 1 && list.get(i).is == 1){
                    real.is = 1;
                    real.x--;
                    list.get(i).is = 0;
                }
            }
            if(list.get(down).is == 1)
                list.get(down).is = 0;

            //3단계
            Robot three = list.get(up);
            if(three.x > 0 && three.is == 0) {
                three.is = 1;
                three.x--;
            }
            //4단계
            if(!check(list, k))
                break;
            step++;
        }
        System.out.println(step);
    }
    static boolean check(ArrayList<Robot> list, int k){
        int count = 0;
        for (Robot robot : list) {
            if (robot.x == 0)
                count++;
        }
        return count < k;
    }
}

문제 설명이 빈약해서인지 이해가 굉장히 어려웠습니다.

몇 단계에서 종료하는지 출력하라고 되어 있는데 저는 암만봐도 4단계밖에 안보여서 이 4단계 중에 답이 되어야 하는데 어떤 예제케이스 답이 막 400이 넘고 그래서 이게 당최 뭔말인가... 싶었습니다.

또 3단계에서 로봇을 넣으란 거같은데 왜 테스트 케이스 1번 예제 답이 2단계이지? 이런 말도안되는 딜레마에 계속 빠져있었죠.

그러다 단계가 의미하는 말이 몇 번 루프를 돌았냐 이걸 뜻하는 거였고 로봇은 n단계의 3번째마다 0번 인덱스에 올리게 되니 총 내구도가 0인 인덱스가 k개 이상이면 무조건 break하라는 뜻이었습니다.

그래서 구현은 다했는데 단계를 못맞춰서 조금 수정해주니 시뮬레이션 문제인데도 무려 원큐에! 풀었답니다 ㅎㅎ

풀이를 하기에 앞서, 문제에 대한 설명을 간략히 정리해보겠습니다.

 

# 코드 없는 문제 요약

1. 1번째 단계에서는 로봇과 컨베이어가 같이 움직이므로 이 파라미터를 모두 담기 위한 클래스가 필요합니다.

2. 2번째 단계에서 로봇만 움직인다고 할 때 앞에 있는 로봇의 존재와 내구도를 신경쓰셔야 합니다.

3. 0의 인덱스에서만 로봇을 올릴 수 있고 이동하거나 올릴 때 내구도가 1 감소합니다.

4. 내리는 인덱스에서는 무조건 로봇을 0으로 바꾸어 주셔야 합니다.

코드로 살펴봅시다.

 

import java.util.*;
class Robot{
    int x;
    int is;
    Robot(int x, int is){
        this.x = x;
        this.is = is;
    }
}

x는 내구도, is는 로봇의 존재를 따집니다.

is가 1이면 로봇이 있단거고 없으면 0입니다.

Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = scan.nextInt();
ArrayList<Robot> list = new ArrayList<>();
for(int i = 0; i < n * 2; i++)
    list.add(new Robot(scan.nextInt(), 0));
int up = 0;
int down = n - 1;
int step = 1;

이런 문제에서는 자료구조가 시간 복잡도를 매우 크게 좌지우지 합니다.

시뮬레이션 같이 데이터를 넣었다 빼기에 유연한 자료구조가 좋으므로 ArrayList를 사용합니다.

list에는 입력값에서 주어지는 내구도와 0을 삽입합니다.

up은 로봇 올릴 때, down은 로봇을 내릴 때 작성할 것이며 step은 정답이 될 단계입니다.

각각 단계별로 나누어서 살펴봅시다.

//1단계
Robot now = list.get(list.size() - 1);
list.add(0, now);
list.remove(list.size() - 1);
if(list.get(down).is == 1)
    list.get(down).is = 0;

1단계에서는 컨베이어벨트와 로봇을 함께 움직입니다.

그런데 클래스 안에 저희는 로봇과 내구도를 같이 담기로 했으므로 Robot클래스를 이용해서 풀어봅시다.

먼저 Robot의 now를 제일 마지막 인덱스로 가져와서 저장합니다.

now를 list의 첫 번째 인덱스에 삽입하고 맨 마지막 인덱스는 삭제합니다.

그리고 list의 down인덱스에서(내리는 인덱스에서) 로봇이 있다면 0으로 바꾸어줍시다.

//2단계
Robot zero = list.get(0);
if(zero.is == 0 && zero.x >= 1 && list.get(list.size() - 1).is == 1) {
    zero.is = 1;
    zero.x--;
    list.get(list.size() - 1).is = 0;
}
for(int i = list.size() - 2; i >= 0; i--){
    Robot real = list.get(i + 1);
    //현재 로봇이 없으면
    if(real.is == 0 && real.x >= 1 && list.get(i).is == 1){
        real.is = 1;
        real.x--;
        list.get(i).is = 0;
    }
}
if(list.get(down).is == 1)
    list.get(down).is = 0;

2단계에서는 로봇을 움직일 수 있을 때 이동시킵니다.

그런데 이 로봇을 0인덱스부터 이동시킬게 아니라, 시뮬레이션 상 밑에있는 로봇부터 이동시켜주어야 조금 더 자연스러워집니다.

또한 맨 마지막 인덱스에 대해 0에서의 로봇 존재와 내구도도 같이 체크해야 한다는 점 잊지 않으셔야 겠습니다.

if(zero.is == 0 && zero.x >= 1 && list.get(list.size() - 1).is == 1) {
    zero.is = 1;
    zero.x--;
    list.get(list.size() - 1).is = 0;
}

코드에서 보는 것과 마찬가지로 zero지점에서 로봇이 0이고 내구도가 1이상이며 맨 마지막 로봇이 1일 때 0인덱스에서의 로봇은 1로, 내구도는 1감소, 현재 지점의 로봇은 0으로 바꾸서야 합니다.

or(int i = list.size() - 2; i >= 0; i--){
    Robot real = list.get(i + 1);
    //현재 로봇이 없으면
    if(real.is == 0 && real.x >= 1 && list.get(i).is == 1){
        real.is = 1;
        real.x--;
        list.get(i).is = 0;
    }
}

그리고 그 외의 인덱스들은 for문을 통해 각각 로봇을 이동시키며 내구도를 감소시켜주시면 되겠습니다.

이것 보다 조금 더 시간 복잡도를 줄이는 방법도 존재합니다.

저 같은 경우엔 모든 인덱스에 대해 쓸데없이 로봇의 존재 여부를 따지고 있지만 그러지마시고 로봇이 담겨 있는 인덱스들만 따로 관리하는 것은 어떨까요?

그러기 위해 자료구조를 하나 더 선언해서 사용하셔야 한다는 특징이 있겠지만 여기까지 따라오신다면 금방 해내실 겁니다.

또, 클래스에 인덱스 변수를 추가하여야겠지요.

 

if(list.get(down).is == 1)
    list.get(down).is = 0;

이 부분도 빼먹으심 안됩니다.

다음으로 3단계를 봅시다.

Robot three = list.get(up);
if(three.x > 0 && three.is == 0) {
    three.is = 1;
    three.x--;
}

3번째 단계에선 드디어 로봇을 위에 올릴차례입니다.

이 때 내구도가 0보다 크고 해당 인덱스에 로봇이 없을 때에만 로봇을 올립니다.

올리고 난 뒤 is를 1로 바꾸고 내구도를 감소시킵니다.

if(!check(list, k))
    break;
step++;

 

마지막 4단계에서 check함수로 로봇이 없는 빈 인덱스가 몇 개인지 여부를 따지는 메서드를 구현했습니다.

static boolean check(ArrayList<Robot> list, int k){
    int count = 0;
    for (Robot robot : list) {
        if (robot.x == 0)
            count++;
    }
    return count < k;
}

check메서드는 다음과 같습니다.

list에 있는 로봇을 모두 돌며 x가 0인 것의 개수를 새고 k보다 크면 false를 리턴하여 while문을 빠져나오면 됩니다.

그리고 그대로 step을 출력하시면 끝납니다.

 

여기까지 코드가 68줄이 나왔습니다.

제가 이틀 전 쯤 프로그래머스에서 백준의 테트로미노 같은 bfs문제를 하나 풀었는데 180줄 정도 나오더라구요.

그걸 블로그에 꼭 올려야지 올려야지 하고 지금 2,3일 된 거 같은데 한 2시간 날잡고 다음 포스팅에서 한 번 올려보겠습니다...

복습하기 싫어지는 코드량이에요. ㅠㅠ

감사합니다.