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

문제 설명

• https://www.acmicpc.net/problem/20055
• 주어진 조건대로 구현하는 문제입니다.

접근법

• 무엇을 어떻게 움직여야 할 지 오래 고민했습니다.
  • ConveyorBelt 전체 배열과 Box정보를 담은 List를 구현해야 할까?
  • Box를 담은 ConveyorBelt List를 만들어야 할까?
  • 보여지는 부분만 Window로 표현해야 할까?
• 저는 List 혹은 Array를 움직이는 게 아니라 Two-Pointer와 유사한 방식으로 풀었습니다.
  • ConveyorBelt의 보여지는 부분을 결정하는 Start_idx와 End_Idx로 움직임을 표현했습니다.
  • 벨트가 한 칸 움직이다. == Start_idx와 End_idx가 1 줄어든다.

pseudocode

while(true){

	// 벨트가 움직입니다.
    인덱스가 0이면 다시 끝자리(2*N-1) 값으로, 인덱스가 0이 아니면 -1을 합니다.

	Collections.sort(Boxes); // 박스를 올린 순서대로 정렬합니다.
	가장 처음 올라온 박스가 내리는 곳에 도착했는지 확인합니다.
    
    // 로봇이 이동합니다.
    for(모든 로봇에 대해){ // 위에서 정렬했기 때문에 올린 순서대로 움직입니다.
    	if(다음 칸에 박스가 없고 내구도가 0이 아니라면){
        	박스를 한칸 전진시킵니다.
            해당 칸의 내구도를 1 감소시킵니다.
            해당 칸에 박스가 있다는 걸 표시해 둡니다.
        }else{ // 다음 칸에 박스가 있다면
        	현재 칸에 박스가 있다는 걸 표시해 둡니다.
        }
    }
    
    가장 처음 올라온 박스가 내리는 곳에 도착했는지 확인합니다.
    
    로봇을 올릴 칸의 내구도가 0이 아니라면 로봇을 올립니다.
    
    내구도가 0이된 곳의 개수를 확인합니다.

}

정답

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] arr = new int[2*N];
		for (int i = 0; i < 2*N; i++) {
			arr[i] = sc.nextInt();
		}
		List<Box> Boxes = new ArrayList<Box>();		
		int Start_idx = 0;
		int End_idx = N-1;
		int answer = 0;
		while(true) {


			answer++;
			
			// 벨트가 움직임
			Start_idx = (Start_idx==0)?2*N-1:Start_idx-1;
			End_idx = (End_idx == 0)?2*N-1:End_idx-1;
			Collections.sort(Boxes);			

			if(Boxes.size()!=0 && Boxes.get(0).x == End_idx) {
				Boxes.remove(0);
			}

			// 로봇이 움직임
			boolean[] Belt = new boolean[2*N]; // i번째 위치에 박스가 존재하는지 체크
			for (int i = 0; i < Boxes.size(); i++) {
				int idx = (Boxes.get(i).x==2*N-1)?0:Boxes.get(i).x+1;
				if(!Belt[idx] && arr[idx]>=1) {

					arr[idx]--;
					Boxes.get(i).x = idx;
					Belt[idx] = true;
				}else {
					Belt[Boxes.get(i).x] = true;
				}
			}
			if(Boxes.size()!=0 && Boxes.get(0).x == End_idx) {
				Boxes.remove(0);
			}

			// 로봇을 올림
			if(arr[Start_idx]>=1) {
				Boxes.add(new Box(Start_idx,answer));
				arr[Start_idx]--;				
			}
			
			int cnt = 0;
			for (int i = 0; i < 2*N; i++) {
				if(arr[i] == 0) cnt++;
			}
			if(cnt >= K) {
				break;
			}
		}
		System.out.println(answer);
	}
	
	static class Box implements Comparable<Box>{
		int x;
		int age;

		public Box(int x, int age) {
			super();
			this.x = x;
			this.age = age;
		}

		@Override
		public int compareTo(Box o) {
			// TODO Auto-generated method stub
			return this.age-o.age;
		}

		@Override
		public String toString() {
			return "Box [x=" + x + "]"+"[age="+age+"]";
		}
		
		
	}
}