백준 20055 컨베이어 벨트 위의 로봇 - 삼성 SW 역량 테스트 기출

백준 20055 컨베이어 벨트 위의 로봇 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

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

 

2. 문제 해결에 대한 아이디어

1. 문제에서는 2열의 컨베이어 벨트로 표시했으나, 그럴 필요 없고 ArrayList로 뒤에서 삭제 앞으로 삽입을 하면 된다.

2. 컨베이어의 각 칸에는 내구도와 로봇의 존재 여부를 표시해야 하므로 Tile 클래스를 선언했다.

3. 나머지는 문제에서 요구하는대로 구현하면 된다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	static int N, K;
	static List<Tile> belt = new ArrayList<>();
	static int loopCnt = 1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nk = br.readLine().split(" ");
		N = Integer.parseInt(nk[0]);
		K = Integer.parseInt(nk[1]);
		String[] line = br.readLine().split(" ");
		for (int i = 0; i < line.length; i++) {
			belt.add(new Tile(Integer.parseInt(line[i]), false));
		}

		while (true) {

			// 1 로봇과 벨트가 함께 회전
			Tile last = belt.get(belt.size() - 1);
			belt.remove(belt.size() - 1);
			belt.add(0, last);
			if(belt.get(N - 1).robot)
				belt.get(N - 1).robot = false;

			// 2 먼저 올라온 로봇부터 이동
			for (int i = N - 1; i >= 0; i--) {
				Tile now = belt.get(i);
				if (now.robot) {
					Tile next = belt.get(i + 1);
					if(!next.robot && next.hp > 0) {
						now.robot = false;
						next.hp--;
						next.robot = true;
						if((i + 1) == N - 1)
							next.robot = false;
					}
				}
			}

			// 3 올리는 위치에 내구도가 0이 아니면 로봇 올리기
			Tile first = belt.get(0);
			if(first.hp > 0) {
				first.robot = true;
				first.hp--;
			}

			if(check())
				break;

			loopCnt++;

		}

		System.out.println(loopCnt);
	}

	static boolean check() {
		int cnt = 0;
		for (int i = 0; i < belt.size(); i++) {
			if (belt.get(i).hp == 0)
				cnt++;
		}
		if (cnt >= K)
			return true;
		else
			return false;
	}
}

class Tile {
	int hp;
	boolean robot;

	public Tile(int hp, boolean robot) {
		super();
		this.hp = hp;
		this.robot = robot;
	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 시험장에서 C++로 풀었는데 deque로 풀었었다. 근데 시간초과가 났었다.. 왜 났는지 모르겠다.

2. 이번에 풀 때도 처음에 컨베이어 벨트를 LinkedList로 구현했다가 시간 초과가 발생했었다.

3. LinkedList는 특정 index 접근 시 처음부터 접근을 해서 시간초과가 난 것으로 생각된다.