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

문제 : 풍선 터트리기

기본적인 내용

핵심은 끝까지 남기려는 풍선을 기준으로 좌,우 구간의 최소값을 구했을때(leftMin, rightMin),
터트리려는 풍선의 값은 두 최소값 보다 크지 않아야합니다.
한번은 작은 풍선을 터트릴 수 있기 때문에 터트리려는 풍선이
좌,우 최소값중 하나 보다는 클 수 있어도, 둘 보다 커버리면 남길 수 없습니다.
Only one max = 큰 수는 하나 까지만 허용
좌에서 우로 최소값을 갱신하며 배열에 넣고, 우에서 좌로 동일하게 해주고
마지막에 두 최소값 보다 크지않나 보면서 확인해줍니다. 그래서 O(3n)의 방법으로 푸는 방법입니다.
나아가서 두 최소값 중 큰것보다 작기만 하면 되기 때문에 O(n)까지 줄일 수 있습니다.

처음 생각한 방법

배열을 처음부터 반복하면서 값을 기준으로 오른쪽과 왼쪽 배열을 만들어 그들의 최소값과 값을 비교하며 계산을 하였다.

function solution(a) {
    var answer = a.length;
    for(let i=0;i<a.length;i++)
        {
            let front =[];
            let back = [];
            front = a.slice(0,i);
            back = a.slice(i+1,a.length);

            if(Math.min.apply(null,front) <a[i] && Math.min.apply(null,back) <a[i]){
                answer--;
            }
        }
    return answer;
}

시간초과 , 런타임 별걸 다 경험했다...

질문 내용에서의 정보

O(n)을 만들기 위해서 오른쪽 끝과 왼쪽 끝에 값부터 시작해
값이 안될 경우는 두 양쪽 값에서 큰값을 기준으로 leftMin이면 오른쪽으로 한칸,rightMin이면 왼쪽으로 한칸갔을 때 해당 값이 leftMin일때 혹은 rightMin일때보다 크다면 불가능한 것으로 찾아낸다.

ex)
5, 10, 8 이 있으면 왼쪽은 5 오른쪽은 8인데 5 < 8 이므로 8에서 왼쪽으로 한칸 갔을때 10은 적어도 오른쪽의 최소값 8보다 크고 왼쪽의 최소값 5보다 크므로 존재할 수 없다.

ex)
10, 18 , 2이 있으면 왼쪽은 10 오른쪽은 2인데 10 < 2 이므로 10에서 오른쪽으로 한칸 갔을때 18은 적어도 오른쪽의 최소값 2보다 크고 왼쪽의 최소값 10보다 크므로 존재할 수 없다.

질문을 토대로 만든 정답 코드

function solution(a) {
    let val = 0;
   let answer = a.length;
   let leftMin = a[0],rightMin = a[a.length-1];
    let leftIndex = 0, rightIndex = a.length-1;
    while(1){
        if(val === a.length-2)				//왼쪽 오른쪽 맨끝을 제외한 횟수반복
            break;
        if(leftMin < rightMin){				//왼쪽min보다 오른쪽min이 클때 
            if( a[--rightIndex] < rightMin  ) 		//오른쪽에서 찾은 값이 오른쪽 최소값보다 작다면 최소값을 갱신
                rightMin = a[rightIndex];
            else 					//오른쪽에서 찾은 값이 오른쪽 최소값보다 크다면 왼쪽 최소값보다도 크므로 최후까지 남길 수 없는 풍선이므로 값을 줄인다.
                answer--;
        }
        else{						//오른쪽min보다 왼쪽min이 크다면
           if(leftMin > a[++leftIndex])		//왼쪽에서 찾은 값이 왼쪽 최소값보다 작다면 최소값을 갱신
                leftMin = a[leftIndex];
            else					//왼쪽에서 찾은 값이 왼쪽 최소값보다 크다면 오른쪽 최소값보다도 크므로 최후까지 남길 수 없는 풍선이므로 값을 줄인다.
                answer--;
        }
        val++;
    }
    return answer;
}

느낀점

진짜 이렇게 어떻게 생각하나 싶다.