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

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

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

 

예전에 문제를 해결하지 못해서 다른 풀이를 참고하여 글을 정리했는데, 다시 풀어보니 기존 방식이 이해가 안가서 해당 블로그를 참조하여 새롭게 풀이를 정리합니다.

 

각 자리 풍선이 최후까지 남아있는지 확인 하기 위해서 현재 위치가 i라고 했을 때, (0 ~ i - 1)의 최소값과 (i + 1 ~ 끝)의 최소값을 비교합니다. 현재 위치의 풍선보다 왼쪽과 오른쪽의 풍선이 둘다 작으면 해당 풍선은 최후까지 남아있을 수 없습니다. (인접한 풍선 중 번호가 더 작은 걸 최대 1번만 터트릴 수 있으므로)

 

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

int solution(vector<int> a) {
    int answer = 2; // 양쪽 끝은 무조건 남아있을 수 있다.
    // a의 사이즈가 3보다 작으면 양쪽 끝이거나 둘 중 하나이므로, a의 크기를 리턴
    if(a.size() < 3) return a.size();
    vector<int> right = a;
    
    // 오른쪽 끝에서 부터 각 자리의 최소값 저장
    for(int i = a.size() - 2; i > 0; i--) {
        right[i] = min(right[i], right[i + 1]);
    }
    
    // 왼쪽부터 최후까지 남을 수 있는지 확인
    int left = a.front();
    for(int i = 1; i < a.size() - 1; i++) {
        // 현재 위치를 기준으로 왼쪽과 오른쪽 풍선보다 모두 큰 경우 최후까지 남을 수 없음
        if(!(a[i] > left && a[i] > right[i])) answer++;
        left = min(left, a[i]);
    }
    
    return answer;
}