1. 문제 설명

• 2N 길이의 컨베이어 벨트 (N *2)
  로봇을 올리는 위치: 1번칸(인덱스: 0)
  로봇을 내리는 위치: N번칸(인덱스: N-1)
• 로봇을 내린다? 벨트에서 완전히 제거 (밑 라인으로 이동 X)
• 각 칸은 내구도를 가짐
  로봇을 올리는 위치에 올리거나, 로봇이 어떤 칸으로 이동하면
  그 칸의 내구도는 1만큼 감소함
• 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료
  → 몇 번째 단계에서 진행이 멈추는가?

컨테이너 벨트의 작동 과정

1. 컨베이어 벨트의 회전
   벨트는 각 칸 위에 있는 로봇과 함께 회전함
2. 회전 후 로봇의 이동
   가장 먼저 올라간 로봇부터, 회전 방향으로 1칸 이동 가능하다면 이동, 아니라면 가만히 있음

• 로봇의 이동 조건:
  이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 함

3. 로봇 올리기
   올리는 위치의 내구도가 0이 아니면 가능
4. 내구도가 0인 칸의 개수 ≥ K → 종료

• 내구도 감소 조건:
  로봇을 올리는 위치에 올리거나 / 로봇이 어떤 칸으로 이동할 경우, 그 칸의 내구도 —

// [input]
3 2
1 2 1 2 1 2

// [output]
2

2. 스크래치

문제 유형 파악: 시뮬레이션

주어진 환경에서 여러 작업을 순차적으로 실행

상태 변화와 규칙에 따라 동작을 구현

1. 상태 변화 관리 & 규칙의 순차적 처리

• 컨베이어 벨트의 회전 → 벨트의 내구도, 로봇의 위치가 변화함
• 회전 이후 로봇 이동, 로봇 추가, 로봇 제거의 작업이 발생

1. 종료 조건

• 문제에서 주어진 K ≤ 내구도가 0인 칸의 개수

3. 풀이

[로직] 문제 쪼개기

// [input]

// [logic]
// 로봇의 배열 & 스텝수 정의
boolean[] robots = new boolean[N];
int step = 0; 

while(true) {
	// 스텝 수 증가
	step ++;
	
	// 1. 벨트 회전 -> 내구도, 로봇 배열 변화
	
	// 2. 회전 후 로봇의 이동 조건 확인 -> 이동 가능하다면 & 이동 후 로봇의 위치 & 내구도 처리
	
	// 3. 로봇 올리기 조건 확인
	
	// 4. 종료 조건 확인 -> break를 통해 while문 탈출
}

// [output]: step 수 출력

1. 벨트 회전

		    int last = belt[2*N-1];
		    System.arraycopy(belt, 0, belt, 1, 2*N-1); // System.arraycopy(src,srcPos,dest,destPost, length)
		    belt[0] = last;

		    boolean[] newRobots = new boolean[N];
		    for(int i=0; i<N-1; i++) newRobots[i+1] = robots[i];
		    robots = newRobots;
		    robots[N-1] = false; // 마지막 위치에 오면 내림

• belt 배열 회전
  마지막 원소 값을 저장한 후, 원ㅇ본 배열을 복사해 0번째 인덱스에 마지막 원소값 씌우기
• robots 배열 변화
  새로운 배열 newRobots 배열에 1칸씩 당겨진 값을 저장
• 마지막 위치(N-1인덱스)에서의 로봇 제거

2. 로봇의 이동

		    for(int i=N-2; i>=0; i--){
		        if(robots[i] && !robots[i+1] && belt[i+1]>0){
		            robots[i]=false;
		            robots[i+1]=true;
		            belt[i+1]--;
		        }
		    }
		    robots[N-1] = false;

• 가장 먼저 올라간 로봇부터 뒤로 1칸씩 이동 → 뒤에서부터 for문으로 처리
• i번째 위치 한 로봇 → i+1의 위치로 옮기기
• 옮긴 위치 (i+1)의 내구도 감소시키기
• for문으로 모든 로봇을 옮긴 후 N-1에 위치한 로봇 제거하기 (내리기)

3. 로봇 올리기

		    if(belt[0]>0 && !robots[0]){
		        robots[0]=true;
		        belt[0]--;
		    }

• 조건: 0번 인덱스의 내구도가 0보다 크고 로봇이 없을 경우
• 로봇을 올리고 내구도 1 감소시키기

4. 종료 조건

				int zeroCount = 0;
		    for(int val : belt) if(val==0) zeroCount++;
		    if(zeroCount >= K) break;

4. 코드

public class Main {
	static int N,K;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
		
		// [input]
		String[] tmp = br.readLine().split(" ");
		N = Integer.parseInt(tmp[0]);
		K = Integer.parseInt(tmp[1]);
		
		// 0-based
		String[] temp = br.readLine().split(" ");
		int[] belt = new int[2*N];

		for(int i=0; i<N*2; i++) {
			belt[i] = Integer.parseInt(temp[i]);
		}
		
		// [logic]
		boolean[] robots = new boolean[N];

		int step = 0;
		while(true){
		    step++;
		    
		    // 1. 벨트 회전
		    int last = belt[2*N-1];
		    System.arraycopy(belt, 0, belt, 1, 2*N-1); // System.arraycopy(src,srcPos,dest,destPost, length)
		    belt[0] = last;

		    boolean[] newRobots = new boolean[N];
		    for(int i=0; i<N-1; i++) newRobots[i+1] = robots[i];
		    robots = newRobots;
		    robots[N-1] = false; // 마지막 위치에 오면 내림

		    // 2. 로봇 이동
		    for(int i=N-2; i>=0; i--){
		        if(robots[i] && !robots[i+1] && belt[i+1]>0){
		            robots[i]=false;
		            robots[i+1]=true;
		            belt[i+1]--;
		        }
		    }
		    robots[N-1] = false;

		    // 3. 로봇 올리기
		    if(belt[0]>0 && !robots[0]){
		        robots[0]=true;
		        belt[0]--;
		    }

		    // 4. 종료 조건
		    int zeroCount = 0;
		    for(int val : belt) if(val==0) zeroCount++;
		    if(zeroCount >= K) break;
		}

		// 출력
		System.out.println(step);

		
	}
}

5. De-fault

fault-1. 배열의 회전: 내구도 배열

배열 회전 방법

1. 배열 복사 (System.arraycopy(src,srcPos,dest,destPost, length) )
2. 큐(Deque) 자료구조 사용

			  // 배열을 오른쪽으로 1칸 회전
        int last = deque.removeLast();  // 마지막 요소 제거
        deque.addFirst(last);           // 마지막 요소를 첫 번째로 추가

        // 배열을 왼쪽으로 1칸 회전
        int first = deque.removeFirst();  // 첫 번째 요소 제거
        deque.addLast(first);             // 첫 번째 요소를 마지막으로 추가

fault-2. 로봇을 이동시킬 때: for문 처리

로봇의 이동은 벨트가 회전한 후 뒤에서 앞으로 이동해야 하므로 for문을 뒤에서부터 작성해야 함

뒤에서부터 처리해야 하는 이유?

앞에서부터 처리할 경우 이미 이동한 로봇을 덮어쓰게 되어 로봇이 이동하지 않는 오류가 발생

시간 복잡도

1. 벨트 회전 (O(N))
   System.arraycopy(belt, 0, belt, 1, 2*N-1)를 사용한 배열의 회전
2. 로봇 이동 (O(N))
   한 번에 벨트의 크기 N 만큼 반복
3. 로봇 올리기 (O(1))
   한 번의 조건 체크와 연산
4. 종료 조건 체크 (O(N))
   belt 배열을 1번 순회

⇒ 각 시뮬레이션 단계에서 수행하는 연산은 최대 O(N) 시간이 걸림

시뮬레이션을 최대 K번 반복해야 하기 때문에, 전체 시간 복잡도는 O(N * K)

이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요.
알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂