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

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

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

 

풀이

 

이 문제는 a의 크기가 1,000,000 이하이기 때문에 시간초과에 유의해야 하는 문제입니다.

 

"왼쪽, 오른쪽 모두에 자신보다 작은 값이 존재하는 경우 절대 남길 수 없다." 라는 규칙이 있습니다. (사실 몰라서 질문게시판에서 힌트 얻음)

따라서 저는 위와 같이 3개의 for문을 사용해 문제를 해결하였습니다.

 

자세한 내용은 주석을 참고하세용

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

using namespace std;

int solution(vector<int> a) {
    int check;       //왼, 오 최솟값에 이용
    
    vector<int> del;        //삭제가능여부 저장 - 가능: 0 / 불가능: 1
    del.resize(a.size());
    fill(del.begin(), del.end(), 1);    //1로 초기화
    
    int answer = 0;
    //왼쪽 확인
    for(int i=0; i<a.size(); i++){
        //맨 왼쪽값
        if (i==0){
            check = a[i];
            del[i] = 0;             //왼쪽에 아무 값도 없음
        }
        
        
        else{
            
            //지금 풍선이 왼쪽 값들 중 최솟값보다 작음
            if(check > a[i]){
                check= a[i];   //최솟값 업데이트
                del[i] = 0;         //왼쪽에 자신보다 큰 값이 있으므로 삭제 가능
            }
            
        }
    }
    
    //오른쪽 확인
    for(int i=a.size()-1; i>=0; i--){
        //맨 오른쪽값
        if (i== a.size()-1){
            check = a[i];
            del[i] = 0;             //왼쪽에 아무 값도 없음
        }
        
        else{
            
            //지금 풍선이 오른쪽 값들 중 최솟값보다 작음
            if(check > a[i]){
                check = a[i];       //최솟값 업데이트
                del[i] = 0;         //오른쪽에 자신보다 큰 값이 있으므로 삭제 가능
            }
            
        }
    }
    
    //삭제가능한 풍선수 count
    for(int i=0; i<del.size(); i++){
        if(del[i] == 0){
            answer++;
        }
            
    }
    
    return answer;
}