[11509] 풍선 맞추기 Javascript

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

11509번: 풍선 맞추기

 

문제를 보면 아래 그림처럼 화살을 쏘면 높이가 하나씩 낮아지면서 풍선을 없애는 것이다. 여기서 새 화살을 쏘는 개수를 구하는 것이다

 

아래 코드 주석 처럼 처음 쏘는 화살이면 높이를 저장해 주면서 풍선을 맞출 때마다 -1을 해주는 형식으로 이중 for문으로 구현했다.

 

const fs = require('fs');
const PATH =
  process.platform === 'linux' ? '/dev/stdin' : './baekjon/input.txt';

const input = fs.readFileSync(PATH).toString().trim().split('\n');

const n = +input[0];
const data = input[1].split(' ').map(Number);

let currentHeight;
let result = 0;
for (let i = 0; i < n; i++) {
  if (data[i] === -1) continue; // 해당 높이에 풍선이 없으면 다음 풍선 진행
  currentHeight = data[i] - 1; // 처음 화살을 쏴서 마출 풍선의 높이 - 1을 해줌 새 화살을 던질때 해당 높이의 풍선을 맞췄기 때문
  result++;
  for (let j = i + 1; j < n; j++) { // 다음 풍선 끝까지 확인
    if (data[j] === currentHeight) {  // 해당 높이에 풍선이 있다면
      currentHeight--; // 현재 화살 높이 - 1
      data[j] = -1; // 해당 풍선을 없애줌
    }
  }
}
console.log(result);

 

하지만 새로운 풀이를 보고 새로워서 포스팅 했다.

각 화살의 높이를 저장하는 방식으로 풀었다. 

풍선의 배열을 하나씩 도는데 한 풍선의 높이에 화살이 없으면 해당 높이의 - 1 한 높이에 +1을 해준다. 예를 들어

5라는 높이에 풍선이 있는데 현재 쏜 화살이 없으면 해당 풍선을 없애주고 풍선을 맞추면 높이가 - 1이 되니깐, -1 한 높이에 화살을 +1 해준다. 그럼 만약 다음 풍선의 높이를 가져왔을 때 다음 풍선의 높이가 4라면 해당 높이에는 화살이 있으니깐 - 1을 해주는 방식으로 화살을 옮긴다고 생각하면 된다.

 

즉 화살의 높이를 하나씩 옮겨준다고 생각하면 된다.

const fs = require('fs');
const PATH =
  process.platform === 'linux' ? '/dev/stdin' : './baekjon/input.txt';

const input = fs.readFileSync(PATH).toString().trim().split('\n');
const n = +input[0];
const data = input[1].split(' ').map(Number);

const height = new Array(1000001).fill(0);
let result = 0;
for (const x of data) {
  if (height[x] > 0) { // 해당 높이에 화살이 있다면 해당 풍선의 높이를 -1을 해주며, 맞췄으니 -1 칸에 +1을 해줌
    height[x] -= 1;
    height[x - 1] += 1;
  } else { // 해당 높이에 화살이 없다면
    height[x - 1] += 1;
    result++; // 화살 쏘기
  }
}

console.log(result);

 

어떻게 이런 발상을 하지??? 신기하네