🔎 풍선 터뜨리기

❓ 문제링크

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

📄 제출 코드

function solution(a) {
  var answer = new Set;
  let len = a.length;
  let left = [];
  let right = [];
  let lmin = a[0];
  let rmin = a[len-1];

  left = a.map((el) => {
    return lmin = Math.min(lmin, el);
  })
  right = a.reverse().map((el) => {
    return rmin = Math.min(rmin, el);
  })
  for (let i = 0; i < len; i++) {
    answer.add(left[i]);
    answer.add(right[i]);
  }

  return answer.size;
}
let a = [-16, 27, 65, -2, 58, -92, -71, -68, -61, -33];
// let a = [9, -1, -5]
console.log(solution(a));

처음에 문제를 이해를 제대로 못해서 어떻게 풀어야할지 해맷다.
마지막에 남는 수중에 어떤 수를 구하는게 아니고, 남는 경우가 몇갠지 구해라? 모든 경우를 다 구하여 답을 구할 수 도 있지만 a의 범위가 그러기엔 심상치않았다.
그러다 결국 질문 게시판을 통해 접근법을 보게 되었다. (장재준님 감사합니다.)

-질문게시판-
기준이 되는 숫자의 좌측, 우측에 모두에 기준보다 작은 숫자가 있으면 터트릴 수 없습니다.

즉, 좌측에만 작은 숫자가 있거나, 우측에만 작은 숫자가 있거나, 양쪽 모두에 없을 경우에 터트릴 수 있습니다.

시간 초과가 나오지 않으려면 좌측, 우측에 값을 체크하는 방법에 신경을 써야 합니다.

좌측 기준으로 최솟값을 찾고, 우측 기준으로 최솟값을 찾으면서 값을 갱신하는 방법으로 통과 할 수 있습니다.

마지막 줄이 핵심이다.
좌측 기준으로 첫번째값을 시작으로 최소값을 찾고, 우측은 끝값을 시작으로 최소값을 left와 right에 넣고, answer를 Set으로 만들어 중복제거가 되게 만들고, 마지막에 answer의 size를 리턴하여 답을 구했다.
처음엔 반복문으로 작성하고 통과를 확인한 후 map을 사용해 고쳤다.