[BEAKJOON / node.js] 11509 풍선 맞추기

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

// test.txt
5
4 5 2 1 4

sol1 - 시간 초과❌

let [N,...input] = require('fs').readFileSync('test.txt').toString().trim().split('\n');
function solution(N,input) {
  let arr = input[0].split(' ').map(Number);
  let answer = 0;
  
  while(Math.max(...arr) !== 0) {
    let top = Math.max(...arr);
    let topIndex = arr.indexOf(top);
    for(let i=topIndex+1;i<N;i++) {
      if(arr[i] === top-1) {
        top--;
        arr[i] = 0;
      }
    }
    arr[topIndex] = 0;
    answer++;
  }
  return answer;
}
console.log(solution(N,input));
// 3

입력값이 큰 줄 모르고 화살을 쏠 때마다 배열을 처음부터 돌게했다. 입력값이 낮다면 sol2보다 조금은 빠르지만 값이 커질수록 큰 차이가 난다. 나름 논리는 풍선 배열에서 화살을 맞아 터진 요소는 0으로 만들고 모든 요소가 0이 될 때까지 쏜 화살의 개수를 출력하게 했다.

 

sol2

let [N,...input] = require('fs').readFileSync('test.txt').toString().trim().split('\n');
function solution(N,input) {
  let arr = input[0].split(' ').map(Number);
  let arrows = Array.from({length:1000000},()=>0);
  let answer = 0;
  for(let i of arr) {
    if(arrows[i]) {
      arrows[i]--;
      arrows[i-1]++;
    } else {
      answer++;
      arrows[i-1]++;
    }
  }
  return answer;
}
console.log(solution(N,input));
//3

시간 복잡도 O(n)을 만들기 위해서 map을 사용해 보고 싶었는데 구현하지 못했고,, C 언어로 된 답안들을  참조해 만들었다.

 

1.

let arrows = Array.from({length:1000000},()=>0);

화살의 높이를 담기 위해 만들었다.

2.

  let answer = 0;
  for(let i of arr) {
    if(arrows[i]) {
      arrows[i]--;
      arrows[i-1]++;
    } else {
      answer++;
      arrows[i-1]++;
    }
  }

처음 for문에 들어오면 else 문에 걸리고 화살 개수를 추가한다. 첫 풍선을 맞추고 시작했으니, i-1에 화살을 담아둔다.

이후 화살이 존재하는 높이에 풍선을 만나면 화살 높이를 낮추고, 날아가는 화살보다 높은 풍선이 있으면 화살을 추가하는 식으로 끝까지 진행한다.