LV.3 풍선 터트리기 JS

문제

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

프로그래머스

풀이 과정

첫 번째 - 시간초과

큰 풍선은 무한대로 터트릴 수 있고 작은 풍선은 터트리고 나면 다음번에 연속해서 작은 풍선을 터트릴 수 없다.

그러면 살리고 싶은 풍선을 고르고 해당 풍선을 기점으로 왼쪽의 최소값과 오른쪽의 최솟값을 찾아서 살리고 싶은 풍선이 양쪽의 최솟값 풍선보다 크다면 해당 풍선은 터지고 그게 아니라면 생존할 수 있다.

그리고 양쪽 끝에 있는 풍선과, 최소값을 가지는 풍선은 무조건 생존할 수 있다.

 

타겟 풍선을 기준으로 양쪽에 있는 풍선을 조금이라도 빨리 찾으려고 따로 정렬된 풍선 배열을 만들고, 해당 풍선의 IDX를 가지는 object를 만들었다. 양쪽 끝 풍선이거나 최솟값을 가지는 풍선을 제외하고 왼쪽, 오른쪽의 최솟값 풍선을 찾고 마지막 조건문을 통해 검사를 한다.

 

제출하니까 시간초과가 난다 ㅠㅠㅠ 계속해서 계선을 해보려 했지만, 최악의 경우 O(n²)의 시간복잡도를 가져서 이렇게 푸는게 아닌 거 같아 새로운 방식을 찾았다.

function solution(a) {
    var answer = 0;
    if (a.length === 1) return 1
    if (a.length === 2) return 2
    let sortA = [...a];
    sortA.sort((a,b) => a-b)
    const idxObj = {}
    for (let i = 0; i < a.length; i++) idxObj[a[i]] = i;

    for (let i = 0; i < a.length; i++){
        if (i === 0 || i === a.length - 1 || sortA[0] === a[i]) answer++;
        else {
            let left;
            let right;
            for (let j = 0; j < sortA.length; j++){
                if (!left && idxObj[sortA[j]] < i) left = idxObj[sortA[j]];
                else if (!right && idxObj[sortA[j]] > i) right = idxObj[sortA[j]];
                if (left !== undefined && right !== undefined) break;
            }
            if (!(a[i] > a[left] && a[i] > a[right])) answer++;
        }
    }
    return answer;
}

두 번째 - 정답

다른 분의 풀이를 봤는데 진짜 천재인 거 같다...

일단 타겟 풍선은 양쪽의 최솟값 풍선보다 한쪽이라도 작으면 무조건 생존할 수 있다. 따라서 왼쪽 끝, 오른쪽 끝에서 시작하는 두 개의 배열(left, right)을 만든다. 그런 다음 양쪽 끝의 풍선은 무조건 생존하기 때문에 아래와 같이 값을 넣어준다.

left[0] = a[0]

right[len - 1] = a[len - 1]

그리고 왼쪽 배열은 왼쪽에서 출발하면서 현재 풍선과 left 배열의 이전 풍선을 비교하면서 현재 풍선이 더 작다면 생존할 수 있는 풍선이 되는 거다.

오른쪽 배열도 마찬가지이므로 똑같이 해주고 마지막으로 중복을 제거한 풍선 개수를 출력한다.

function solution(a) {
    var answer = 0;
    const len = a.length
    const left = Array(len);
    const right = Array(len);
    left[0] = a[0];
    right[len - 1] = a[len - 1];
    for (let i = 1; i < len; i++) left[i] = Math.min(left[i - 1], a[i]);
    for (let j = len - 2; j >= 0; j--) right[j] = Math.min(right[j + 1], a[j]);
    
    return new Set([...left, ...right]).size;
}