풍선 터트리기

• 링크(https://programmers.co.kr/learn/courses/30/lessons/68646)

문제풀이

풍선이 남아 있을 수 있으려면, 왼쪽 풍선과 오른쪽 풍선을 확인해서, 작은 풍선을 1번만 터트리는 경우를 찾아야한다.
그래서, 두 가지 배열을 만들어야한다. 배열의 인덱스가 현재 풍선 위치라고 가정하고,

1. 왼쪽에서부터 현재 인덱스 전까지 남아있는 왼쪽 풍선은 무엇인지 저장하고 있는 배열을 만든다.
2. 오른쪽에서부터 현재 인덱스 전까지 남아있는 오른쪽 풍선은 무엇인지 저장하고 있는 배열을 만든다.
3. 그 다음 각 풍선을 돌면서, 왼쪽, 오른쪽의 풍선을 확인하여 현재 풍선이 터질 수 있는지 확인하면 된다.

  예제 : [-16,27,65,-2,58,-92,-71,-68,-61,-33]인 경우
  현재 지점에서 왼쪽 풍선이 어떠한 풍선이 남는지 배열을 만든다면(새로운 배열의 1번째 원소는 -16으로 시작)
  1. -16 vs 27 -> [-16,-16,0,0,0,0,0,0,0,0]
  2. -16 vs 65 -> [-16,-16,-16,0,0,0,0,0,0,0]
  ...
  5. -16 vs -92 -> [-16,-16,-16,-16,-16,-92,0,0,0,0]
  ...
  9. -92 vs -33 -> [-16,-16,-16,-16,-16,-92,-92,-92,-92,-92]

  위와 같은 배열이 만들어진다.
  그리고 이와 동일하게 오른쪽에 대해서도 똑같이 배열을 만들면 된다.

  left = [-16,-16,-16,-16,-16,-92,-92,-92,-92,-92]
  right = [-92,-92,-92,-92,-92,-92,-71,-68,-61,-33]

  이렇게 두개의 배열을 만들고,
  [-16,27,65,-2,58,-92,-71,-68,-61,-33] 배열을 돌면서 확인해주면 된다.(첫번째, 마지막은 빼고 돌린다.)
  i=1인 27의 경우 left[0] , right[2]를 확인
  i=2인 65의 경우 left[1] , right[3]을 확인
  ...

---

• 첫번째, 마지막 풍선은 항상 터질 수 있다.

소스코드

const log = console.log;
function solution(a) {

    let answer = 0;
    let len = a.length;
    let left = Array(len).fill(0);
    let right = Array(len).fill(0);
    left[0] = a[0];
    right[len-1] = a[len-1];
    for(let i=1 ; i<a.length ; i++){
        if(a[i] > left[i-1]) left[i] = left[i-1];
        else left[i] = a[i];
    }
    for(let i=len-2 ; i>=0 ; i--){
        if(right[i+1] < a[i]) right[i] = right[i+1];
        else right[i] = a[i];
    }
    
    for(let i=1 ; i<len-1 ; i++){
        if(left[i-1] < a[i] && a[i] > right[i+1]) continue;
        answer++;
    }
    answer+=2;
    return answer;
}