[Javascript/PGS] Lv.3 : 풍선 터트리기

 

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

프로그래머스

---

프로그래머스 레벨 3. 

규칙을 찾아서 적용시켜야 한다

난 이런 수학/패턴 유형이 좀 새롭게 느껴져서 어려운 것 같다...🥹

그래서 힌트 참고했다 ㅎㅎ

 

내가 참고한 글은시간초과 걱정 없는 풀이 방법이다.

단 한번만 작은 풍선을 터트릴 수 있다는 점에서, 이 기회를 마지막으로 남겨두고

맨 마지막에 2개가 남았을 때 작은 풍선을 터트리거나, 이 기회를 버리고 큰 풍선을 터트리면 된다.

그러려면, 마지막 이전에는 항상 큰 수가 사라져야 한다(작은 수만 살아남음)

 

(1) 맨 마지막에 2개가 남았을 때 작은 풍선을 터트리려면 -> 남은 작은 풍선이 최솟값이어야 함

(2) 마지막 2개에서 이 기회를 버리고 큰 풍선을 터트리면 -> 최솟값이 살아남음 (따라서 이 최솟값은 항상 살아남을 수 있다)

 

(3) 따라서 최솟값 min을 구한 뒤, 이 min은 살아남을 수 있으므로 answer = 1로 설정해준다.

(4) 이후 0 ~ min-1, end ~ min+1 까지의 범위에서 항상 더 작은 수만 살아남게 한다. (만나는 숫자와 본인 중 큰 수를 터트림)

 

참고 내용

출처 : https://school.programmers.co.kr/questions/77305

 

 

나의 풀이

function solution(a) {
    var answer = 0;
    if(a.length<3) return a.length;
    let minValue = Infinity;
    let minIdx;
    answer = 1;
    for(let i=0; i<a.length; ++i){
        if(minValue>a[i]){
            minValue = a[i];
            minIdx = i;
        }
    }
    
    let big = Infinity;
    for(let i=0; i<minIdx; ++i){
        if(big>=a[i]){
            big = a[i];
            answer++;
        }
    }
    
    big = Infinity;
    for(let i=a.length-1; i>minIdx; --i){
        if(big>=a[i]){
            big = a[i];
            answer++;
        }
    }
    
    return answer;
}