[백준]컨테이너 벨트 위의 로봇 20055 - JAVA

1. 문제

 

2. 접근

문제를 읽어보면 특정 알고리즘을 이용하는 것이 아니라 구현 문제임을 알 수 있다. 계속 구현 문제를 풀면서 느낀 것은 구현 문제는 처음부터 잘 구현해야한다!! 그렇지 않으면 디버깅 시간이나 실수 고치는 시간이 더 드는 것 같다.

 

그래서 구현 문제임을 파악하고 구체적인 설계부터 시작했다.

끄적 설계

 

문제에서 친절하게 각 단계마다 설명을 줘서 단계별로 함수를 나눴다.

고민한 점은 내려가는 위치, 올라가는 위치를 담을 고정 위치 정보, 움직이는 벨트 정보, 인형의 정보를 겹치지 않고 어떻게 저장할까 였다.

 

class를 너무 많이 만들면 오히려 헷갈려서 최대한 줄이면서 표현하려고 했다. 처음엔 int[] 배열로 각 벨트의 내구도를 저장하고 `Doll` 클래스로 인형의 생성카운트, 현재 위치를 저장했다.

 

하지만 2번 단계인 인형의 움직임을 구현하면서 벨트와 인형의 정보가 따로 있으면 안되는 것을 깨달았다. 왜냐하면 인형이 움직이는 조건이 다음 칸에 인형이 없어야하고, 벨트의 내구도 1이상이어야 해서 하나의 데이터로 관리해야 꼬이지 않을 것 같았다. 또한 문제를 다시보니 N+1칸부터는 인형이 오는 경우가 전혀 없었다. 인형의 생성 시간대로 전진을 해야해서 우선 순위 큐를 쓰려고 했는데 그럴 필요없이 N-1칸부터 0번째 칸을 탐색하면 되는 것이었다.

 

그래서 최종으로는 `Belt` 클래스 하나를 정의해서 내구도 정보, 칸 위에 인형의 존재 여부를 저장했다.

class Belt{
    int durability;
    boolean isDoll;

    public Belt(int durability, boolean isDoll) {
        this.durability = durability;
        this.isDoll = isDoll;
    }
}

 

 

3. 구현

1. 벨트와 함께 로봇 이동

할 때마다 어려운 배열 돌리기... 하나 하나 손으로 그려가면서 식을 찾았다. 2차원 배열을 1차원 배열로 관리해서 힘들었다.

public static void moveBelt(){
        Belt temp = belts[N-1];

        for(int i=N-1; i>=1; i--){
            belts[i] = belts[i-1];
        }
        belts[0] = belts[N];
        for(int i=N; i<= 2*N-2; i++){
            belts[i] = belts[i+1];
        }
        belts[2*N-1] = temp;

        belts[N-1].isDoll = false;
    }

 

2. 로봇 이동

쉬운 줄 알았는데 주관적인 해석이 섞여서 계속 의심됐던 함수다. 내리는 위치에 도착하면 즉시 로봇이 내려가는데 이때 내구도가 깎이는지 안깎이는지 엄청 애매했다.

public static void moveDolls(){
        for(int i=N-2; i>=0; i--){
            // 벨트에 인형이 없음
            if(!belts[i].isDoll)
                continue;

            // 내리는 칸에 도착
            if(i == N-2 && belts[i+1].durability > 0){
                belts[i].isDoll = false;
                belts[i+1].durability--;
                continue;
            }

            if(belts[i+1].durability > 0 && !belts[i+1].isDoll){
                belts[i].isDoll = false;

                belts[i+1].isDoll = true;
                belts[i+1].durability--;
            }
        }
    }

 

3. 로봇 올리기

// 3. 로봇 올리기
            if(belts[0].durability > 0){
                belts[0].isDoll = true;
                belts[0].durability--;
            }

 

4. 내구도가 0인 칸의 개수 확인

public static int getZeroDurabilityNumber(){
        int count = 0;
        for(int i=0; i<2*N; i++){
            if(belts[i].durability <= 0){
                count++;
            }
        }
        return count;
    }

 

이렇게 총 4가지 함수로 끝!

 

4. 전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int N, K;
    static Belt [] belts;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        belts = new Belt[2*N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            belts[i] = new Belt( Integer.parseInt(st.nextToken()), false); // 내구도 초기화
        }
        for(int i=2*N-1; i>= N; i--){
            belts[i] = new Belt( Integer.parseInt(st.nextToken()), false); // 내구도 초기화
        }

        int step = 0;
        while(true){
            step++;

            // 1. 벨트와 함께 로봇 이동
            moveBelt();

            // 2. 로봇 이동
            moveDolls();

            // 3. 로봇 올리기
            if(belts[0].durability > 0){
                belts[0].isDoll = true;
                belts[0].durability--;
            }

            // 4. 내구도 칸 확인
            if(getZeroDurabilityNumber() >= K){
                break;
            }
        }
        System.out.println(step);
    }

    public static void moveBelt(){
        Belt temp = belts[N-1];

        for(int i=N-1; i>=1; i--){
            belts[i] = belts[i-1];
        }
        belts[0] = belts[N];
        for(int i=N; i<= 2*N-2; i++){
            belts[i] = belts[i+1];
        }
        belts[2*N-1] = temp;

        belts[N-1].isDoll = false;
    }

    public static void moveDolls(){
        for(int i=N-2; i>=0; i--){
            // 벨트에 인형이 없음
            if(!belts[i].isDoll)
                continue;

            // 내리는 칸에 도착
            if(i == N-2 && belts[i+1].durability > 0){
                belts[i].isDoll = false;
                belts[i+1].durability--;
                continue;
            }

            if(belts[i+1].durability > 0 && !belts[i+1].isDoll){
                belts[i].isDoll = false;

                belts[i+1].isDoll = true;
                belts[i+1].durability--;
            }
        }
    }

    public static int getZeroDurabilityNumber(){
        int count = 0;
        for(int i=0; i<2*N; i++){
            if(belts[i].durability <= 0){
                count++;
            }
        }
        return count;
    }
 }
class Belt{
    int durability;
    boolean isDoll;

    public Belt(int durability, boolean isDoll) {
        this.durability = durability;
        this.isDoll = isDoll;
    }
}

계속 테케와 틀린 답이 나와서 고민을 많이 했다. 의심스러웠던 2번 함수만 수십 번 봤는데 정작 문제는 벨트의 내구도를 입력받을 때 2층부터는 뒤에서부터 저장해야하는데 냅다 한 줄도 저장해서 생긴 문제였다. 설계를 열심히 하였지만 중간 중간 계속 수정되고 다시 오랜 디버깅의 늪에 빠져버렸다... 언젠간 좋아지겠지!