문제
풀이
요구사항
2N개의 칸으로 나누어진 컨베이어 벨트가 있고 각 칸에는 내구도가 있다. 내구도가 0인 칸의 개수가 K개 미만이 될 때까지 벨트를 회전시키고, 최종적으로 벨트의 회전 횟수를 출력하라.
한번의 회전에서는 아래의 동작들이 순서대로 수행된다.
- 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
- 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
2-1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다. - 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
- 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
올리는 위치란 컨베이어 벨트의 1번째 칸을 말하며, 내리는 위치란 컨베이어 벨트의 N번째 칸을 말한다.
또한 아래와 같은 조건들이 있다.
- 로봇은 올리는 위치에만 올릴 수 있다.
- 로봇은 내리는 위치에 도달하면 그 즉시 내린다.
- 로봇을 올리면 올린 위치의 내구도가 1 감소한다.
- 로봇이 한 칸 이동하면 이동한 칸의 내구도가 1 감소한다.
해결방안
2N길이의 1차원 배열을 생성해서 컨테이너 벨트라고 가정한다. 각 칸의 값으로는 내구도가 들어있다. (입력 값으로 들어온 내구도 정보를 그대로 사용하면 된다.)
const durability = input[1].split(' ').map(Number);내구도가 0인 칸의 개수를 확인하기 위해 zero라는 변수를 만들고, 회전 횟수를 누적하기 위해 answer 변수를 만든다.
let zero = 0;
let answer = 0;또한 각 칸에 로봇이 있는지 없는지 판별할 수 있어야 하기 때문에 robots라는 배열을 만든다.
로봇은 내리는 위치, 즉 N번 칸에서 내리고, 1번 칸에서 올리기 때문에 N+1 ~ 2N 까지는 신경쓰지 않아도 된다. 따라서 robots 배열의 길이는 N으로 설정해준다.
const robots = Array(N).fill(false);이제 컨베이어 벨트가 한 칸 회전하는 부분을 rotate 라는 함수로 구현한다. 이 함수는 내구도가 0인 칸의 개수가 K개 미만이 될 때까지 반복 수행된다.
while (zero < K) {
rotate();
answer++;
}이제 rotate 함수를 구현해보자.
컨베이어 벨트의 회전은 배열을 dequeue한 다음 dequeue한 값을 enqueue함으로써 구현해줄 수 있다.
이때, 큐 자료구조를 직접 구현해줘도 좋았겠지만, N의 범위가 작기 때문에 그냥 unshift 를 사용했다.
// 내구도 한 칸씩 이동
let temp = durability.pop();
durability.unshift(temp);컨베이어가 회전함에 따라 위에 있던 로봇도 같이 회전할 수 있도록 한다. 로봇이 한 칸 앞으로 이동하는 것을 moveFoward라는 함수로 구현해서 재사용성을 높인다.
// 로봇 한 칸씩 이동
for (let i = N - 2; i >= 0; i--) {
if (robots[i]) {
moveFoward(i);
}
}i를 뒤에서부터 탐색하는 이유는 앞에서부터 탐색할 경우 로봇이 한 칸 앞으로 이동했을 때, i가 증가하며 이미 이동한 로봇을 또다시 이동시키기 때문이다.
moveFoward함수는 index를 인수로 받아서 다음 칸을 true로 만들고 현재 칸을 false로 만든다. 만약 다음 칸이 내리는 칸이라면 현재 칸만 false로 만든다.
function moveFoward(index) {
// 로봇이 이동했을 때 내리는 위치라면
if (index + 1 === N - 1) {
robots[index] = false;
} else {
robots[index + 1] = true;
robots[index] = false;
}
}이제 맨 앞에 있는 로봇부터 앞으로 이동할 수 있으면 이동하도록 해준다. 이동한 칸은 내구도가 1 감소하고, 만약 내구도가 0이라면 zero를 1 증가시킨다.
// 첫 번째 로봇부터 이동할 수 있으면 이동
for (let i = N - 1; i >= 0; i--) {
// i번째 칸에 로봇이 있다면 (N-1번째 칸은 false임이 보장됨)
if (robots[i]) {
// 앞에 로봇이 없고, 내구도가 1 이상이라면
if (!robots[i + 1] && durability[i + 1] >= 1) {
moveFoward(i);
durability[i + 1]--;
if (durability[i + 1] === 0) zero++;
}
}
}올리는 위치에 로봇을 올릴 수 있다면 올려준다.
// 올리는 위치에 로봇을 올릴 수 있다면 올리기
if (durability[0] > 0) {
robots[0] = true;
durability[0]--;
if (durability[0] === 0) zero++;
}아래는 전체 코드다.
코드
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);
const durability = input[1].split(' ').map(Number);
const robots = Array(N).fill(false);
let zero = 0;
let answer = 0;
function rotate() {
// 내구도 한 칸씩 이동
let temp = durability.pop();
durability.unshift(temp);
// 로봇 한 칸씩 이동
for (let i = N - 2; i >= 0; i--) {
if (robots[i]) {
moveFoward(i);
}
}
// 첫 번째 로봇부터 이동할 수 있으면 이동
for (let i = N - 1; i >= 0; i--) {
// i번째 칸에 로봇이 있다면 (N-1번째 칸은 false임이 보장됨)
if (robots[i]) {
// 앞에 로봇이 없고, 내구도가 1 이상이라면
if (!robots[i + 1] && durability[i + 1] >= 1) {
moveFoward(i);
durability[i + 1]--;
if (durability[i + 1] === 0) zero++;
}
}
}
// 올리는 위치에 로봇을 올릴 수 있다면 올리기
if (durability[0] > 0) {
robots[0] = true;
durability[0]--;
if (durability[0] === 0) zero++;
}
}
function moveFoward(index) {
// 로봇이 이동했을 때 내리는 위치라면
if (index + 1 === N - 1) {
robots[index] = false;
} else {
robots[index + 1] = true;
robots[index] = false;
}
}
while (zero < K) {
rotate();
answer++;
}
console.log(answer);
