[백준 | JavaScript] 10810 공 넣기

<문제 설명>

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 들어있지 않으며, 바구니에는 공을 1개만 넣을 수 있다.

도현이는 앞으로 M번 공을 넣으려고 한다. 도현이는 한 번 공을 넣을 때, 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약, 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고, 새로 공을 넣는다. 공을 넣을 바구니는 연속되어 있어야 한다.

공을 어떻게 넣을지가 주어졌을 때, M번 공을 넣은 이후에 각 바구니에 어떤 공이 들어 있는지 구하는 프로그램을 작성하시오.

 

<입출력>

<문제 풀이>

const fs = require("fs");
let input = fs.readFileSync("./input.txt").toString().split('\n')
let len = input[0].split(' ').map(Number)
let arr = new Array(len[0]).fill(0)

for (let i = 1; i < input.length; i++) {
    let num = input[i].split(' ').map(Number)
    for (let j = num[0] - 1; j < num[1]; j++) {
      arr[j] = num[2]
    }
  }
let answer = arr.join(' ')

console.log(answer)

입력 첫째 줄은 각각 몇 개를 입력할 것인지, 몇을 입력할 것인지 구분한다.

둘째 줄부터는 [0]~[1]의 요소에 [2]를 넣는데, 중복되면 갱신한다.

 

공이 들어있지 않으면 0을 출력하므로, 기본적으로 빈 배열에 0을 넣어주고 시작했다. 

위의 입출력을 예를 들어, 1 2 3 이면, 첫 번째 ~ 두 번째 요소까지 모두 3을 넣는다는 것이다.

그럼 3 3 0 0 0이 된다. 3 4 4는 3~4번째 요소에 4를 넣는다. 3 3 4 4 0이 된다.

1 4 1 은 1~4번째 요소에 1을 넣는다. 1 1 1 1 0 이 된다. 

2 2 2 는 2~2번째 요소에 2를 넣는다. 1 2 1 1 0이 된다. 

 

입력이 1 2 3 이런 식으로 공백으로 구분되어있기 때문에 반복문으로 숫자를 검사할 때 

num이라는 변수를 만들어 split(' ')으로 공백으로 나누어주었고, 각 요소를 숫자로 만들었다. 

num은 1 2 1이 변해 [1,2,1]이 되겠다. 이중 반복문으로 num을 확인해 answer을 출력한다.

[1,2,1]에서는 1~2번째 요소를 바꾸기 때문에, 배열의 인덱스는 -1을 해주어야 한다.

 

arr은 처음에 0,0,0,0,0 처럼 0으로 세팅되어 있다.

그래서 num[0]-1부터 num[1]전까지의 값, 1~2라면 0~1번 인덱스를 바꾸어주는 것이다.

이후 1 4 1이 나오면 1~4번째 요소 즉, 0~3번 인덱스를 1로 바꾸어주는 것이다. 

이를 갱신하고 반복해서 answer이 반환된다.

 

<코멘트>

문제를 풀면서 가장 먼저 생각난 것은, 어차피 마지막에 입력된 값만 필요하기 때문에,

중복되는 값을 굳이 반복해서 구할 필요가 없다는 것이다.

1~2를 3으로 바꾸고, 3~4를 4로 바꾸지만 그 다음에 1~4를 1로 바꾸니까 결국 1로 다 채워진다.

그리고 그 중 두번째는 다시 2로 바뀌었다. 기존에 무엇을 입력했든 상관이 없다. 

 

그렇다면 거꾸로 올라가면서 값이 갱신되려 할 때 무시하면 되지 않나? 하는 생각이 들었다.

dp를 사용해서 풀 수 있을지 고민해봐야겠다.