[JS] 풍선 터트리기

문제

프로그래머스

 

풀이

이번 문제는 탐색이다. 하지만 입력되는 배열의 길이가 100만으로 매우 긴 모습을 알 수 있다.

 

이렇게 입력이 큰 문제의 경우 시간복잡도를 고려한 풀이 설계가 필요하다.

 

문제를 읽어보면 한 풍선의 양쪽 풍선 중 하나만 터트릴 수 있으며, 두 풍선 중 작은 풍선을 터트리는 것은 한번만 가능하다.(큰 풍선을 터트리는 것은 횟수 제한이 없다)

 

필자는 최종적으로 남는 풍선의 관점으로 풀이를 진행했다.

 

맨 마지막에 남는 풍선은 왼쪽 혹은 오른쪽의 풍선들보다 작은 수를 갖어야 한다.

이러한 점을 이용해 투 포인터 알고리즘을 적용해 마지막에 남을 수 있는 지 검증했다.

 

또한 작은 풍선을 터트리는 경우는 한번 뿐이기에 두개의 포인터 중 작은 포인터는 유지하고 큰 포인터만 움직이며 검증을 진행했다. (어짜피 작은 포인터를 유지하면 마지막에 만나게 되니까)

 

코드

const solution = (a) => {
  const answer = [];
  let [lp, rp] = [0, a.length - 1];
  let [lm, rm] = [a[lp], a[rp]];
  while (true) {
    if (lm > rm) {
      if (lm > a[lp + 1]) {
        answer.push(a[lp + 1]);
        lm = a[lp + 1];
      }
      lp += 1;
    }
    else if (lm < rm) {
      if (rm > a[rp - 1]) {
        answer.push(a[rp - 1]);
        rm = a[rp - 1];
      }
      rp -= 1;
    }
    if (rp - lp === 1) break;
  }
    
  return answer.length + 2;
};