프로그래머스 - 풍선 터트리기(Lv.3)

문제 풀이

• 최후까지 남을 수 있는지를 각 원소에 대해서 확인한다.
• 배열의 양 끝에 있는 원소는 최후까지 남기는 것이 언제나 가능하다.
• 확인하고자 하는 원소( val )의 좌측 서브 배열, 우측 서브 배열의 최솟값을 구했을 때 val 보다 큰 값이 하나라도 있다면 최후까지 남을 수 있다.

구현(시간초과)

#include <string>
#include <vector>

using namespace std;

int find_min(vector<int>& a, int start, int end){
    int min = a[start];
    for(int i=start+1; i<=end; i++){
        if(min > a[i]) min = a[i];
    }
    
    return min;
}

bool check_final_possible(vector<int>& a, int left_start, int left_end, int right_start, int right_end, int val){
    // 1. Left, Right에서 최솟값을 찾는다.
    // left_min, right_min 둘다 val보다 작다면 false 반환
    int left_min = find_min(a, left_start, left_end);
    int right_min = find_min(a, right_start, right_end);
    if(val>left_min && val>right_min) return false;
    else return true;
}

int solution(vector<int> a) {
    int n = a.size();
    if(n==1) return 1;
    else if(n==2) return 2;
    
    int left_start, left_end, right_start, right_end;
    int cnt=2;
    for(int i=1; i<n-1; i++){
        left_start = 0; left_end = i-1;
        right_start = i+1; right_end = n-1;
        if(check_final_possible(a, left_start, left_end, right_start, right_end, a[i]))
            cnt++;
    }

    
    return cnt;
}

개선한 점

• 매번 최솟값을 찾는 것이 아니라, 다이나믹 프로그래밍을 활용한다.
• dp_front[i]는 0번~i번 인덱스의 범위에서의 최솟값을, dp_back[i]는 (n-1)~(n-i)번 인덱스의 범위에서의 최솟값을 담는다.

구현(All pass)

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

using namespace std;

bool check_final_possible(vector<int>& dp_front, vector<int>& dp_back, int val, int idx){
    int n = dp_front.size();
    int front = idx-1;
    int end = n-1-front-1;
    
    int left_min = dp_front[front];
    int right_min = dp_back[end];
    
    // cout << "dp_front idx: " << front << " dp_back index: " << end << endl;
    if(val>left_min && val>right_min) return false;
    return true;
}

// Debugging
void print_dp(vector<int>& dp1, vector<int>& dp2){
    cout << "------dp front-----\n";
    for(auto ele:dp1){
        cout << ele << " ";
    }
    cout << endl;
    cout << "------dp back-----\n";
    for(auto ele:dp2){
        cout << ele << " ";
    }
    cout << endl;
}

int solution(vector<int> a) {
    int n = a.size();
    if(n==1) return 1;
    else if(n==2) return 2;
    
    // dp_front[i]는 0~i 범위에서의 최솟값
    // dp_back[i]는 (n-1) ~ (n-i) 범위에서의 최솟값
    int cnt=2;
    vector<int> dp_front(n), dp_back(n);
    dp_front[0] = a[0]; dp_back[0] = a[n-1];
    for(int i=1; i<n; i++){
        dp_front[i] = a[i]<dp_front[i-1] ? a[i] : dp_front[i-1];
        dp_back[i] = a[n-1-i]<dp_back[i-1] ? a[n-1-i] : dp_back[i-1];
    }
    
    // print_dp(dp_front, dp_back);
    
    for(int i=1; i<n-1; i++){
        if(check_final_possible(dp_front, dp_back, a[i], i))
            cnt++;
    }
    
    return cnt;
}