[프로그래머스 lv3] 풍선 터트리기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

 

해설

a의 풍선들 중에서 주어진 규칙으로 풍선을 터뜨렸을 때 최종적으로 남을 수 있는 풍선의 수를 구하는 문제이다.

a의 i번째 풍선이 최종적으로 남을 수 있는지 어떻게 확인할 수 있을까?

 

1) 문제에서 인접한 풍선들끼리만 비교하여 터뜨릴 수 있다고 했으므로, a[i]의 오른쪽에 있는 풍선들을 비교하여 터뜨린다면 a[i]의 오른쪽에는 가장 작은 풍선만 남는다. 마찬가지로, a[i]의 왼쪽에 있는 풍선들을 비교하여 터뜨리면 a[i]의 왼쪽에는 가장 작은 풍선만 남는다.

 

2) 풍선들을 터뜨릴 때 작은 풍선을 터뜨릴 수 있는 기회는 최대 한번뿐이다. 따라서, a[i]의 왼쪽에 있는 풍선들 중 가장 작은 풍선,  a[i]의 오른쪽에 있는 풍선 중 가장 작은 풍선 중에서 a[i]보다 작은 것의 개수가 2개 미만이라면 살아남을 수 있는 해당 풍선은 살아남을 수 있다.

 

3) a[i]의 왼쪽에 있는 가장 작은 풍선과 a[i]의 오른쪽에 있는 가장 작은 풍선은 누적 최솟값으로 O(N)에 구할 수 있다. 왼쪽부터 출발했을 때 인덱스 i까지의 최솟값을 lmn[i], 오른쪽부터 출발했을 때 인덱스 i까지의 최솟값을 rmn[i]로 구해두고 a[i]와 lmn[i-1], lmn[i+1]을 비교하면 된다.

 

a를 순회하면서 a[i]가 살아남을 수 있는지 확인하고 살아남을 수 있는 풍선의 개수를 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int n;
int lmn[1000005];
int rmn[1000005];

int solution(vector<int> a) {

    n = (int)a.size();

    lmn[0] = a[0];
    for (int i=1; i<n; i++)
        lmn[i] = min(lmn[i-1], a[i]);

    rmn[n-1] = a[n-1];
    for (int i=n-2; i>=0; i--)
    rmn[i] = min(rmn[i+1], a[i]);

    int ans = 0;
    for (int i=0; i<n; i++) {
        int cnt = 0;
        if (i >= 1 && lmn[i-1] < a[i]) cnt++;
        if (i+1 < n && rmn[i+1] < a[i]) cnt++;
        if (cnt < 2) ans++;
    }

    return ans;
}