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

 이 문제는 스택을 이용해서 풀었다. 일단 입력 배열의 최대 길이가 100만이므로 O(n) 이하 알고리즘을 사용해서 시간 안에 풀 수 있다. 이 문제에서 핵심은 임의의 두 풍선을 선택했을 때, 결국 둘 중 하나만 터진다는 것이다. 즉, 만약 1,2,3,4,5 라는 풍선이 있고 둘 중 무조건 큰 풍선만이 터진다고 하면 순서에 상관없이 1이 나오는 것처럼, 숫자가 많거나 짝수거나 홀수거나는 중요하지 않고 결국 제일 작은 값이 남는다는 것이다. 이를 이용하면, a 배열에 대해 i 인덱스에서 왼쪽에 있는 수 중 작은 수가 존재하고, 오른쪽에 있는 수 중에도 작은 수가 존재한다면 한번만 작은 수의 풍선을 터트려서는 불가능하다.

 

 

 그 다음은 이 원리를 구현하는 방법인데, 우선순위 큐, 이분 탐색 등 다양한 생각을 했지만 결국 원본 배열을 정렬할 수 없어 불가능했다. 그러다가 스택을 떠올렸고, 스택에 있는 상태는 i 인덱스 기준 i - 1 부터 0번째까지의 노드들이라고 생각하고 수도코드를 짰다.

for 0 -> n - 1
	while (!st.empty() && a[st.top()] > present) 
		cnt[st.top()]++ // 이전 노드들 중에서 나보다 작은게 없다 -> 이전 노드들은 전부 나보다 큰수 -> cnt++
		st.pop()
	// 만약 스택이 비었다 -> 이전 노드 모든 것이 나보다 큰 수들 -> 아무일도 안일어남
	만약 스택이 비지 않고 남아있다 // 이전 노드 중 나보다 작은게 존재
		cnt[present]++
	st.push(present)

 이렇게 짜면 cnt 배열에서 2인 값은 오른쪽, 왼쪽 둘 다 작은 값이 존재하므로 정답이 아니고, 2보다 작은 값인 것만 answer++ 해주면 정답이 나오게 된다.

 

 

#include <string>
#include <vector>
#include <stack>

using namespace std;

#define MAX 1000000

int cnt[MAX];

int solution(vector<int> a) {
    int answer = 0;
    
    // base case
    if (a.size() == 1 || a.size() == 2) {
        return a.size();
    }
    
    stack<int> st;
    
    for (int i = 0; i < a.size(); i++) {
        int present = a[i];
        
        while (!st.empty() && a[st.top()] > present) {
            cnt[st.top()]++;
            st.pop();
        }
        
        if (!st.empty()) {
            cnt[i]++;
        }
        st.push(i);
    }
    
    for (int i = 0; i < a.size(); i++) {
        if (cnt[i] < 2) {
            answer++;
        }
    }
    
    return answer;
}