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

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/68646?language=cpp 

프로그래머스

 

이번 문제는 다이나믹 프로그래밍(DP) 또는 스택(stack) 문제였습니다.

 

 

 

 

 

 

1. 다이나믹 프로그래밍 DP

📝 문제 풀이

1. 각 풍선의 왼쪽 최솟값(leftMin)과 오른쪽 최솟값(rightMin)을 저장할 배열 선언

• leftMin[0]은 a 벡터의 첫번째 값으로 초기화
• rightMin[n-1]은 a 벡터의 마지막 값으로 초기화

2. for 문을 돌며 각 풍선의 왼쪽 최솟값과 오른쪽 최솟값을 구함

3. 풍선의 번호가 왼쪽 최솟값이나 오른쪽 최솟값보다 작거나 같으면 최후까지 남을 수 있으므로 answer++ ⭐️

 

 

 

 

👩🏻‍💻 C++ 코드 

#include <string>
#include <vector>
#define MAX 1000000

using namespace std;

int leftMin[MAX];
int rightMin[MAX];

int solution(vector<int> a) {
    int answer = 0;
    int n = a.size();
    
    leftMin[0] = a[0];
    rightMin[n-1] = a[n-1];
    
    // 각 풍선의 왼쪽 최솟값 구하기
    for (int i=1; i<n; i++) {
        if (a[i] < leftMin[i-1]) {
            leftMin[i] = a[i];
        } else {
            leftMin[i] = leftMin[i-1];
        }
    }
    
    // 각 풍선의 오른쪽 최솟값 구하기
    for (int i=n-2; i>=0; i--) {
        if (a[i] < rightMin[i+1]) {
            rightMin[i] = a[i];
        } else {
            rightMin[i] = rightMin[i+1];
        }
    }
    
    for (int i=0; i<n; i++) {
        if (a[i] <= leftMin[i] || a[i] <= rightMin[i]) answer++;    
    }
    
    return answer;
}

 

프로그래머스 - 결과 화면

 

 

 

 

 

 

2. 스택 (stack)

📝 문제 풀이

1. answer을 a 벡터의 크기로 초기화

2. 스택 top의 풍선 번호보다 현재 풍선 번호가 더 작으면 스택 top의 풍선을 터트릴 수 있으므로 s.pop() ⭐️

3. 배열 끝에 있는 풍선은 언제나 살아남을 수 있으므로 스택이 비어있지 않을 때에만 answer--

4. while문이 종료될 때마다 현재 풍선 번호를 스택에 삽입

 

 

 

 

👩🏻‍💻 C++ 코드

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

using namespace std;

int solution(vector<int> a) {
    int answer = a.size();
    stack<int> s;
    
    for (int i=0; i<a.size(); i++) {
        while (!s.empty() && s.top() > a[i]) {
            s.pop();
            
            // 배열의 끝에 있는 풍선은 항상 살아남을 수 있음
            if (!s.empty()) answer--;
        }
        
        s.push(a[i]);
    }
    
    return answer;
}

 

프로그래머스 - 결과 화면