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

문제

https://programmers.co.kr/learn/courses/30/lessons/68646

풀이

검색하려는 값(target) 기준으로 좌, 우 배열의 최솟값 left, right을 구하고 최솟값들이 target 보다 크다면 성공, 하나만 작다면 찬스를 이용해 성공, 둘 다 작다면 실패입니다.

• 첫 번째 방법.
  배열을 순회하면서 terget 기준으로 배열을 자르고 left, right를 구했습니다. 이 경우 시간복잡도 O(n^2) 으로 시간 초과 발생합니다.

    const leftMin = Math.min.apply(null, a.slice(0, idx));
    const rightMin = Math.min.apply(null, a.slice(idx + 1, len));

• 두 번째 방법
  시간 복잡도를 O(n)으로 줄이기 위해 target 값 기준 좌, 우의 최솟값을 저장하는 배열을 생성 후 비교를 통해 answer++

 	 leftArray = [-16,-16,-16,-16,-16,-92,-92,-92,-92,-92]
	 	 a = [-16, 27, 65, -2, 58,-92,-71,-68,-61,-33]
	rightArray = [-92,-92,-92,-92,-92,-92,-71,-68,-61,-33]

코드

function solution(a) {
  if (a.length < 3) return a.length;

  let answer = 0;
  let leftArray = [];
  let rightArray = [];
  let leftMin = a[0];
  let rightMin = a[a.length - 1];

  a.forEach((_, idx) => {
    leftMin = leftMin < a[idx] ? leftMin : a[idx];
    leftArray.push(leftMin);

    rightMin = rightMin < a[a.length - 1 - idx] ? rightMin : a[a.length - 1 - idx];
    rightArray.push(rightMin);
  });

  rightArray.reverse();

  a.forEach((value,idx)=>{
    const left = leftArray[idx];
    const right = rightArray[idx];
    const target = value;
  
    if (left === target || right === target) answer++;
  })

  return answer;
}

// const a = [-16, 27, 65, -2, 58, -92, -71, -68, -61, -33];
// solution(a);