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

 

https://programmers.co.kr/learn/courses/30/lessons/68646

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

기본적인 아이디어.

​

i 번째 풍선의 왼쪽 방향의 최종 남는 풍선은,

i 번째 풍선의 왼쪽 방향 풍선들 중 가장 작은 값의 풍선이 남는다.

마찬가지로

i 번째 풍선의 오른쪽 방향의 최종 남는 풍선은,

i 번째 풍선의 오른쪽 방향 풍선들 중 가장 작은 값의 풍선이 남는다.

​

그 후 최종적으로 i 번째 풍선과 양옆의 풍선이 남아있는 경우

양옆의 풍선의 값이 i 번째 풍선의 값보다 하나 이상 큰 값이 존재하면

그 i 번째 풍선은 남을 수 있다.

​

이러한 과정을 풍선 배열의 크기만큼 반복하여야 한다.

그러므로 leftmin[], rightmin[]의 배열을 미리 세팅하여 사용한다.

(풍선 배열의 크기만큼 반복하는 동안 양옆 풍선의 최소값과 최대값을 반복해서 구하면 오버타임 뜰 가능성이 높다)

 

 

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


//https://programmers.co.kr/learn/courses/30/lessons/68646
int solution(vector<int> a) {
    int answer = 0;
    int rightmin[a.size()]; //i번쨰 풍선의 오른쪽 풍선들중 가장 작은값
    int leftmin[a.size()]; //i번쨰 풍선의 왼쪽 풍선들중 가장 작은값
    int mymin;
    
    
    leftmin[0]=1000000001; //극단 세팅
    rightmin[a.size()-1]=1000000001; //극단 세팅
    
    mymin=a[0];
    for(int i=1; i<a.size(); i++)
    {
        if(a[i-1]<mymin)
        {
            mymin=a[i-1];
        }
        leftmin[i]=mymin; //i번쨰 풍선의 왼쪽 풍선들중 가장 작은값
    }
    
    mymin=a[a.size()-1];
    for(int i=a.size()-2; i>=0; i--)
    {
        if(a[i+1]<mymin)
        {
            mymin=a[i+1];
        }
        rightmin[i]=mymin; //i번쨰 풍선의 오른쪽 풍선들중 가장 작은값
    }
    
    for(int i=0; i<a.size(); i++)
    {
        if(a[i]<leftmin[i]||a[i]<rightmin[i])  //풍선 판단
        {
            answer++;
        }
    }
    
   
    return answer;
}