[프로그래머스 lev3/JS] 풍선 터트리기

문제 출처

프로그래머스 lev3 - 풍선 터트리기

내 풀이

기본적인 풀이 아이디어.

한번만 큰 값을 남길 수 있고, 나머지 모든 연산은 작은 값을 남긴다는 건,
하나의 요소를 기준으로 왼쪽 오른쪽에는 최솟값이 담길 수밖에 없다는 의미이다.

그래서 왼쪽/오른쪽의 최솟값을 비교해서 둘 중 하나라도 현재 요소보다 크면, 남은 하나의 연산에서 큰 값을 남기는 연산 1개를 수행하면 된다.

그리고 맨 처음 요소와 맨 마지막 요소는 무조건 가능한 남기는 게 가능하므로 answer를 애초에 2로 시작하면 된다.

풀이 1 (시간초과 실패)

원래는
let left = Math.min.apply(Math, slice(0, i))
let right Math.min.apply(Math, slice(i+1))

혹은 전개 연산자로 최솟값을 구하려 했으나 런타임 에러가 계속 발생한다.

for문으로 돌자니 O(n^2)라서 시간초과가 발생한다..

function solution(a) {
  var answer = 2;

  for (let i = 1; i < a.length - 1; i++) {
    const target = a[i];

    let left = Number.MAX_SAFE_INTEGER;
    let right = Number.MAX_SAFE_INTEGER;

    for (let j = 0; j < i; j++) {
      if (a[j] < left) left = a[j];
    }
    for (let j = i + 1; j < a.length - 1; j++) {
      if (a[j] < right) right = a[j];
    }

    // console.log(i, left, target, right);
    if (target < left || target < right) answer++;
  }

  return answer;
}

// console.log(solution([9, -1, -5])); // 3
console.log(solution([-16, 27, 65, -2, 58, -92, -71, -68, -61, -33])); // 6

2차 시도 (성공)

O(n^2)을 O(n)으로 바꾸려면 반복문을 최대한 나누면 된다.

ldp, rdp 배열을 각각 만들어 주고,
두 배열의 [i]에는 최솟값이 계속 업데이트되도록 코드를 작성한다.

이렇게 코드를 작성하면,
ldp[i-1]에는 i 왼쪽의 최솟값이 담기고
rdp[i+1]에는 i 오른쪽의 최솟값이 담기게 된다.

그럼 마지막 반복문에서 더 이상 O(n^2)가 소요되지 않아도 각 배열의 인덱스에 저장된 값만 꺼내서 쓰면 빠르게 최솟값을 비교할 수 있다.

function solution(a) {
  var answer = 2;
  var al = a.length;

  var ldp = [...a];
  var rdp = [...a];

  for (let i = 1; i < al; i++) {
    if (ldp[i] > ldp[i - 1]) ldp[i] = ldp[i - 1];
  }
  for (let i = al - 2; i >= 0; i--) {
    if (rdp[i] > rdp[i + 1]) rdp[i] = rdp[i + 1];
  }

  for (let i = 1; i < al - 1; i++) {
    // console.log(a, a[i], ldp[i - 1], rdp[i + 1]);
    if (a[i] < ldp[i - 1] || a[i] < rdp[i + 1]) {
      answer++;
    }
  }

  return answer;
}