[node.js] 백준 10810번 공 넣기

1. 문제 해석

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

10810번: 공 넣기

 

바구니안에는 하나의 공만 들어갈 수 있고 그 공에는 숫자가 적혀있다.

예를들어 1번 바구니에 공3번을 넣었다가 이후에 다시 공5번을 넣으면 1번 바구니에는 공5번만 남아있는 것이다.

N개의 바구니가 주어지는데 M번 공을 넣는 문제이다.

2번째줄부터는 바구니의 범위와 공의 번호가 주어진다.

바구니의 범위에 공의 번호를 넣어주면 되는데, 공은 누적이 되지 않고 교체가 돼야 한다.

 

 

2. 문제 풀이

N개만큼 바구니를 만들어주고 그 속에 번호를 채우기만 하면된다.

new Array(N)을 사용해서 N개만큼 바구니를 만들어주었다. (1번 바구니 = 0번 인덱스, 즉 바구니의 번호는 인덱스 + 1이 된다.)

그리고 바구니에 공을 아예 넣지 않을 경우에는 0을 반환해야 하기 때문에 초기값은 fill을 이용해서 0으로 채워주었다.

주어진 입력을 배열로 변환 후 모두 숫자로 변환해주면 숫자로 된 이중배열을 만들어 준다.

이중 for문을 사용해서 정답으로 사용할 배열에 이중 배열 중 첫번째 인덱스 + 1부터 마지막 인덱스까지 공의 번호로 fill을 해주었다.

fill(채울 숫자 또는 문자, 첫번째 인덱스, 마지막 인덱스 + 1)

예를들어 fill(4, 1, 6) 라고 적용하면 4라는 숫자를 1부터 5(6 - 1)의 인덱스까지 채워지는 것이다.

let newArray = [0, 0, 0, 0, 0, 0, 0].fill(4, 1, 6)

console.log(newArray) // newArray = [0, 4, 4, 4, 4, 4, 0]

 

 

 

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/fill

Array.prototype.fill() - JavaScript | MDN

 

3. 코드

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
let [num, ...inputBastket] = input;
const n = num.split(' ')[0];
const m = num.split(' ')[1];

let newArr = new Array(Number(n)).fill(0);
const changeArr = inputBastket.map((item) => item.split(' '));
const numberArr = changeArr.map((item) => item.map((it) => Number(it)));

for (let i = 0; i < m; i++) {
  for (let j = 0; j < 3; j++) {
    newArr.fill(numberArr[i][2], numberArr[i][0] - 1, numberArr[i][1]);
  }
}

console.log(newArr.join(' '));

반복문이 이중으로 돌아가는 구조는 시간복잡도가 커지기 때문에 다른 방법이 없을지 고민을 했다.

 

for (let i = 0; i < m; i++) {
  const [start, end, value] = inputBastket[i].split(' ').map(Number);
  newArr.fill(value, start - 1, end);
}

fill의 메소드를 이용하는 방법이 있었다. 

인자로 값, 시작인덱스, 마지막인덱스를 받을 수 있기 때문에 비구조화할당을 이용해서 상수로 값을 지정하고 매소드에 상수를 넣어서 활용하는 방법이 있다.

이렇게 적용하면 for문을 한번만 적용해 시간 복잡도를 크게 줄일 수 있었다.