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

문제 링크

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

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

---

C++ 풀이

#include <vector>
using namespace std;

int solution(vector<int> a) {
    if (a.size() < 3)
        return a.size();
    vector <int> right_min = a;

    //오른쪽 끝에서부터 각 자리까지의 최소값을 저장
    for (int i = right_min.size() - 2; i > 0; i--)
        right_min[i] = min(right_min[i], right_min[i + 1]);

    int left_min = a.front();
    int answer = 2; //양 끝은 무조건 남을 수 있음

    //왼쪽부터 차례대로 최후까지 남을 수 있는지 확인
    for (int i = 1; i < a.size() - 1; i++) {
        //마지막 남은 양 옆의 풍선이 모두 작은 경우 최후까지 남을 수 없음
        if (!(a[i] > left_min && a[i] > right_min[i + 1]))
            answer++;

        left_min = min(left_min, a[i]);
    }
    return answer;
}

각 자리 풍선이 최후까지 남을 수 있는지 확인하였다.

확인 방법은 각 자리(i) 기준으로 (0 ~ i - 1)의 최소값, (i + 1 ~ 끝)의 최소값과 비교하였을 때, 최소 1개 이상의 수보다 작은가이다.

작은 수를 없앨 수 있는 찬스가 한 번 있기 때문에 적어도 1개 이상의 수보다 작아야지만 최후까지 남을 수 있다.

 

 

예를 들어 두번째 테스트케이스에서 -71(7번째 풍선)이 최후까지 남을 수 있는지 확인을 원한다면 

-92(1 ~ 6번째 풍선 중 제일 작은 수)와 -68(8 ~ 10번째 풍선 중 제일 작은 수)과 비교를 하면 된다.

-92 < -71 < -68 이므로 1개 수보다 작기 때문에 최후까지 남을 수 있다.