[ 프로그래머스 ] 풍선 터트리기 (C++)

프로그래머스

 

난이도 : Level 3 
알고리즘 유형 : DP 
풀이 시간 : 1시간 15분 

문제 풀이 

어떤 풍선이 최후까지 남아있는지 알아보고싶다. 풍선을 터트릴 수 있는 조건은 다음과 같다.

1. 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트림
2. 풍선들 사이 빈 공간이 있다면, 중앙으로 밀착시킨다.

최후까지 남기는 것이 가능한 풍선들의 개수를 return하자.

 

먼저 입력 배열의 길이를 확인해보면 $a ≤ 1000000$으로 주어지기 때문에 백트래킹, 완전탐색으로 접근할 경우 시간초과가 발생한다. 또한, 정렬을 할 수 없기 때문에 그리디로 문제를 해결하기도 어려워보인다.

따라서, DP를 활용해서 문제를 풀어나가면 된다.

 

먼저, 문제의 가장 중요한 조건으로 "번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다." 가 있다. 이말은 즉슨 최후의 경우에 더 작은 풍선을 터트리면 된다는 것이다. 입출력 예시를 살펴보자.

 

ex1) [ 9, -1, -5 ]

해당 경우에서 -1의 생존 여부를 확인해본다면, 먼저 9와 -1을 비교하여 9를 터트려주고, -1과 -5를 비교하여 더 작은 경우인 -5를 터트리면 -1이 최후까지 남을 수 있다.

 

ex2) [ -9, -1, -5 ]

그렇다면, 해당 경우에 -1이 살아남을 수 있는지 살펴보자. 

먼저 -9와 -1을 비교하면 더 작은 값을 없애는 경우를 한 번 사용하고 -9를 없앤다.

그다음, -1과 -5를 비교하려고 보니 이미 더 작은 값을 없애는 찬스를 한 번 사용했기 때문에 -5를 없애지 못한다. 따라서 -1을 최후까지 남길 수 없다.

 

이를 통해 우리는 다음 규칙을 얻을 수 있다.

풍선이 [ a, b, c ] 가 존재하는 경우에 가운데 풍선(b)을 남기기 위해서는 
1. a < b, b < c
2. a > b, b < c
3. a > b, b > c

위 경우일 때만 가능하다 => b가 작은 순간이 있기만 하면 b는 최후의 풍선이 될 수 있다.

 

그렇다면 이제 구현을 해보자.

 

먼저 두 값을 비교하기 이전에 크기가 큰 풍선들을 모두 없애주어야 한다. 

이를 위해서는 left와 right 배열을 새롭게 만들어서 값을 비교한 다음, 최솟값만 저장해야한다.

그 다음, 현재 a의 인덱스 값과 양쪽 left, right와 값을 비교하여 정답을 구하면 된다.

 

-92는 left, right와 비교했을 때 가장 작기 때문에 최후의 풍선이 될 수 있다.

해당 예시를 살펴보면 a[5]는 left[4]와 right[6]보다 작기 때문에 최후의 풍선으로 선택될 수 있다.

해당 경우에서는 58이 나머지 두 값보다 크기 때문에 터지게 된다.

하지만 해당 경우에서는 a[4] = 58이 나머지 두 값 (left[3], right[5])보다 항상 크기 때문에 최후의 풍선이 될 수 없다.

 

추가로, left[0]과 right[n - 1]은 항상 가능하기 때문에 answer = 2로 초기화를 시킨 뒤 진행하면 된다.

 

시간복잡도로는 최악의 경우, $O(1000000)$이 소요된다.

 

코드

/*
1. 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트림
2. 풍선들 사이 빈 공간이 있다면, 중앙으로 밀착시킨다.

- 번호가 더 작은 풍선은 한 번만 터트릴 수 있음 -> 나머지는 번호가 더 큰 풍선을 터트려야한다.
최후까지 남기는 것이 가능한 풍선들의 개수를 return

a의 길이 <= 1000000

풀이 : 정렬 불가능

먼저 풍선이 큰 녀석들만 모두 터트린다. 
가운데 풍선을 남기기 위해서는 
1. a < b, b < c
2. a > b, b < c
3. a > b, b > c
--> b가 작은 순간이 있기만 하면 answer가 가능하다.
*/

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int left_a[1000001] = {0, };
int right_a[1000001] = {0, };

int solution(vector<int> a) {
    int answer = 0;
    int n = a.size();
    
    if (a.size() == 1)
        return 1;
    
    left_a[0] = a[0];
    right_a[n - 1] = a[n - 1];
    answer = 2;
    
    // 왼쪽부터 최솟값 찾기
    for (int i=1;i<n;i++){
        left_a[i] = min(left_a[i - 1], a[i]);
    }
    
    // 오른쪽 최솟값 찾기
    for (int i=n - 2;i>=0;i--){
        right_a[i] = min(right_a[i + 1], a[i]);
    }
    
    // 최소가 될 수 있는 경우 구하기
    for (int i=1;i<n - 1;i++){
        if (a[i] < left_a[i - 1] || a[i] < right_a[i + 1])
            answer++;
    }
    
    return answer;
}

배운 점 

DP임을 빠르게 인지하고 문제를 구상했지만 생각보다 시간을 많이 소요하였다.

이후, 타 블로그를 참고하여 아이디어를 얻었는데 .. 이번에도 한 끗 차이로 아이디어를 생각하지 못해 아쉬웠다.

DP의 경우 left와 right의 최솟값을 구한 뒤 그 중간에 있는 값이 최소인지의 여부를 따지는 문제도 여럿 존재하기 때문에, 해당 아이디어도 문제를 여럿 풀어봐야겠다.

 

+ 비슷한 문제가 있다면 댓글로 알려주심 감사하겠습니다 !!