백준 11509번 풍선 맞추기 Node.js 풀이

문제 링크

- 내 풀이

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input.shift());

const balloonArr = input[0].split(" ").map(Number);

const arrowArr = Array(N + 1).fill(0);

let answer = 0;

for (let i = 0; i < N; i++) {
  if (arrowArr[balloonArr[i]] > 0) {
    arrowArr[balloonArr[i]] -= 1;
    arrowArr[balloonArr[i] - 1] += 1;
  } else {
    arrowArr[balloonArr[i] - 1] += 1;
    answer += 1;
  }
}

console.log(answer);

여기서 저 arrowArr가 핵심부분이다.

만약 저 arrowArr가 존재하지 않는다면, 2중 반복문을 돌면서 시간복잡도는 O(n^2)가 되는데, 저 arrowArr을 통해 O(n)으로 만들어줄수 있다.

화살을 쐈을때 0보다 크다면, 이전에 이미 화살이 발사가 되었다는 뜻이고 새로운 화살을 발사해줄 필요가 없다.

하지만 arrowArr[인덱스] 값이 0이라면, 처음으로 발사가 된다는 뜻이므로 인덱스에 -1을 한 값에 1을 더해주고 화살 갯수 또한 더해준다.

예를 들어서 4인 화살을 발사했을때, 이전에 발사한 적이 없다면 arrowArr[4]의 값은 0일것이고,

화살은 풍선을 맞춘 후에 높이가 -1 이 되니 arrowArr[3]에 +1을 해준다. 현재 화살은 3의 위치에 있다는 뜻이다.

또 answer에 1을 더해줌으로써 화살의 갯수를 늘려준다.