[JS] 풍선 터트리기

풍선을 터트리는 문제였다 큰 알고리즘 기법이라기 보다는 문제에서 주어진 요구를 잘 읽으면 해결할 수 있는 문제였다. 굳이 말하면 dp라고도 할 수 있을 것 같다.

 

 

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

프로그래머스

 

유의있게 볼만한 조건은 a의 최대길이가 1,000,000으로 이중반복문을 사용하면 안될거란 것과 a의 모든 수는 다르단 것 정도이다.

 

 

 

결국 나보다 작은 풍선을 한번만 터트릴 수 있다는 표현은 , 본인을 제외하고 좌측과 우측의 풍선을 모두 터뜨리면 된다.

 

[-16,27,65,-2,58,-92,-71,-68,-61,-33]

 

예시에서 주어진 위 배열에서 58을 검사한다고 생각해보자. 58을 기준으로 왼쪽과 오른쪽의 풍선을 큰 풍선을 터트리는쪽으로 모두 터트린다면 

 

-16 58 -92 가 남게 된다. 이 경우에는 왼쪽,오른쪽이 모두 본인보다 작기 때문에 어떤 방법으로도 해당 풍선을 터트릴 수 없게 되는 것이다.

 

 

이 과정을 매번 반복하면 시간복잡도에 걸릴게 뻔하니 왼쪽과 오른쪽 각각에서 풍선을 하나씩 터뜨린 결과를 저장하는 배열 2개를 두어서 메모하는 방식으로 해결하였다.

 

 

1. 풍선을 왼쪽부터 {i} 번째까지 터뜨렸을때 남은 풍선의 정보를 저장하는 left생성

2. 풍선을 오른쪽부터 {i}번째까지 터트렸을 때 남은 풍선을 저장하는 right 생성

3. {i} 번째 풍선이 left[i-1] 와 right[i+1] 보다 둘다 크다면 해당 풍선을 터트릴 수 없음

4. 맨 처음 풍선과 맨 마지막 풍선은 어떤경우에도 터트릴 수 있다.

    ㄴ 문제에서 2개이하 입력만 들어오는 경우가 있으니 해당 경우를 예외처리 해주어야 한다.

 

 

 

뭔가 타 3단계에 비해서는 쉬운 문제였다.

 

function solution(a) {
    if(a.length <= 2) return a.length
    const left = Array(a.length).fill(0)
    let tmp = Infinity
    for (let i = 0 ; i < a.length ; i++) {
        if (tmp > a[i])tmp = a[i]
        left[i] = tmp
    }
    tmp = Infinity
    const right = Array(a.length).fill(0)
    for (let i = a.length-1 ; i>=0 ; i--){
        if (tmp > a[i])tmp = a[i]
        right[i] = tmp
    }
    
    let ret = 2
    for (let i = 1 ; i < a.length-1 ; i++){
        if (left[i-1] < a[i] && a[i] > right[i+1]) continue
        ret += 1
    }
    
    return ret
}