[프로그래머스] 68646. 풍선 터뜨리기

문제 링크

[프로그래머스] 68646. 풍선 터뜨리기

풀이 과정

풍선의 위치를 기준으로, 끝까지 남기기 위한 시뮬레이션을 통해 문제를 풀었습니다.

먼저 풍선이 양쪽 사이드에 위치할 때를 살펴보겠습니다. 왼쪽 끝에 위치한 풍선을 끝까지 남기는 방법은 다음과 같습니다.

1. 파란색 괄호로 표시된 우측 나머지 풍선들을 하나가 남을 때까지 계속해서 큰 걸 터뜨린다.
2. 둘 만 남았을 때 무조건 a 를 남길 수 있게 된다.
   • a < x 인 경우 : 큰 걸(x) 터뜨려 a 를 남기자.
   • a > x 인 경우 : 작은 걸(x) 터뜨려 a 를 남기자.

오른쪽 끝에 위치한 풍선을 끝까지 남기는 방법은, 위에 적어 둔 왼쪽 끝에 위치한 풍선을 끝까지 남기는 방법과 같습니다.

다음은 가운데에 껴있는 풍선의 경우를 알아보겠습니다.

1. 풍선 a 를 기준으로 왼쪽과 오른쪽 각각에 대해 풍선이 하나가 남을 때까지 계속해서 큰 걸 터뜨린다.
2. 풍선이 셋 남았을 때, 풍선 a 를 남기기 위한 다음 네 가지의 경우를 보자.
   • x < a < y 인 경우
     1. a 와 y 를 선택해 큰 걸(y) 터뜨린다.
     2. a 와 x 가 남으면, 작은 걸(x) 터뜨린다.
     3. 혹은, 위와 반대로 작은 것부터 터뜨려도 가능.
   • y < a < x 인 경우 :
     1. a 와 x 를 선택해, 큰 걸(x) 터뜨린다.
     2. a 와 y 가 남으면, 작은 걸(y) 터뜨린다.
     3. 마찬가지로, 위와 반대로 작은 것부터 터뜨려도 가능.
   • a < x, y 인 경우
     • x, y 둘 다 a 보다 크므로, x 먼저 터뜨리고 y 를 터뜨리거나, y 먼저 터뜨리고 x 터뜨린다.
   • a > x, y 인 경우
     • x, y 둘 다 a 보다 작으므로, 작은 걸 한 번만 터뜨려야 하는 문제 조건으로는 a 를 남기지 못한다.

let len = a.length;

if(len == 1) return 1;

풍선이 하나면, 1을 리턴합니다.

let answer = 2;
let left = new Array(len),
    right = new 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 i = len - 2; i >= 0; i--) right[i] = Math.min(right[i + 1], a[i]);

풍선이 두 개 이상이라면, 답을 2로 정해 두고 배열 left 와 right 를 생성합니다.

• 풍선이 두 개면, 둘 다 마지막까지 남길 수 있으므로 초기 정답은 2로 설정합니다.
• 세 개 이상이라면, 가운데 껴있는 풍선이 존재하게 됩니다. 양 쪽 부분에서 숫자가 큰 풍선들을 차례로 제거하게 되면, 마지막엔 가장 작은 숫자의 풍선만이 남게 됩니다. 따라서, 각 인덱스까지의 풍선의 최소값을 진행 방향에 맞게 배열 left 와 right 에 저장합니다.

for (let i = 1; i <= len - 2; i++) {
    if ((left[i - 1] < a[i] && a[i] < right[i + 1]) || (right[i + 1] < a[i] && a[i] < left[i - 1]) || (left[i - 1] > a[i] && right[i + 1] > a[i])) answer++;
}

위의 코드는 가운데 껴있는 풍선이 마지막까지 남게 되는 세 가지 경우에 해당하는 지 확인합니다. left[i - 1] 은 껴있는 풍선의 왼쪽 부분에서의 최소값을, right[i + 1] 은 껴있는 풍선의 오른쪽 부분에서의 최소값을 의미합니다. 세 경우에 해당하면 마지막까지 남길 수 있는 풍선이므로, 카운트해줍니다.

코드

function solution(a) {
    let len = a.length;
    
    if(len == 1) return 1;

    let answer = 2;
    let left = new Array(len),
        right = new 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 i = len - 2; i >= 0; i--) right[i] = Math.min(right[i + 1], a[i]);

    for (let i = 1; i <= len - 2; i++) {
        if ((left[i - 1] < a[i] && a[i] < right[i + 1]) || (right[i + 1] < a[i] && a[i] < left[i - 1]) || (left[i - 1] > a[i] && right[i + 1] > a[i])) answer++;
    }

    return answer;
}

solution([9, -1, -5]);
solution([-16, 27, 65, -2, 58, -92, -71, -68, -61, -33]);
solution([1]);