프로그래머스 : 풍선 터트리기 C++

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

코딩테스트 연습 - 풍선 터트리기

후기

1. 완벽하게 풀었다 생각해쓴데 시간초과가 떳다

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> a) {
    int answer = 2;
    int min1;
    int min2;
    for(int i=1;i<a.size()-1;i++)
    {
        min1= 1000000001;
        min2 = 1000000001;
        for(int j=0;j<i;j++)//왼쪽에서 젤 작은거
        {
            min1 = min(min1,a[j]);
        }
        for(int j=i+1;j<a.size();j++)
        {
            min2 = min(min2,a[j]);
        }
        
        if(a[i]> min1 && a[i] > min2)
            continue;
        
        answer++;
    }
    return answer;
}

 

2. 양단 min값을 매 루프마다 안구하고 미리 구해두면 O(n^2)까지 안가도 되겠네!

3) 오른쪽부터 올때의 최솟값이랑 왼쪽일때 각각 구해둠

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> a) {
    int answer = 2;
    int *dp1 = new int[a.size()]; //왼쪽에서부터 최소
    int *dp2 = new int[a.size()]; //오른쪽에서부터 최소
    
    dp1[0] = a[0];
    dp2[a.size()-1] = a[a.size()-1];
    for(int i=1;i<a.size();i++)
    {
        dp1[i] = min(dp1[i-1],a[i]);
    }
    for(int i=a.size()-2;i>0;i--)
    {
        dp2[i] = min(dp2[i+1],a[i]);
    }
    
    
    for(int i=1;i<a.size()-1;i++)
    {
        if(a[i]>dp1[i-1] && a[i] > dp2[i+1])
            continue;
        
        answer++;
    }
    return answer;
}