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

문제

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

프로그래머스

---

문제 해석

- 규칙에 따라 숫자가 붙은 풍선을 터트릴때 최후에 남을 수 있는 풍선들을 구하면 된다.

---

문제 풀이

- 만약 풍선이 3개 남았을때 가운데 풍선이 살아 남지 못하는 경우는 다음과 같다.

  . 좌, 우측 풍선이 가운데 풍선보다 모두 작게 되면 두 풍선 중 작은 풍선을 2번 이상 터트리지 못하기 때문에 가운데 풍선은 살아 남지 못하게 된다.

- 또한 한 풍선의 우측과 좌측에서 가장 작은 풍선은 무조건 최후의 3개의 풍선으로 살아 남을 수 있다.

  . 예를 들어 "3, 4, 5, 2, 53, 23, 12, 5" 의 순으로 풍선이 있을 때 53을 살리고 싶다면 최후의 순간 "2, 53, 5" 처럼 53 풍선 좌우측의 수중 가장 작은 수는 살아 남는다는 것이다.

- 1번째 줄과 2번째 줄을 합치게 되면 한 풍선이 최후까지 살려면 해당 풍선을 가운데 두고 좌우측 수중 가장 작은 수를 남겨 3개의 풍선이 남았 을때 좌우측에 남은 풍선이 둘다 가운데 풍선보다 작으면 해당 풍선은 살아남지 못한다.

  . 예를 들어 "3, 4, 5, 2, 53, 23, 12, 5" 풍선중 53이 살아 남는지 호가인 하려면 "2, 53, 5" 를 남긴 후 2와 5는 52보다 작기때문에 53은 살아남지 못하는 것이다.

- 이를 이용하여 주어진 풍선들을 기준으로 좌측의 풍선중 최소값을 적어둔 "left 벡터"와 반대로 우측의 최소값을 적어 둔 "right" 벡터를 만들어 a[i] 와 left[i], right[i] 를 비교하여 하나라도 a[i] 보다 큰 수가 있으면 해당 풍선은 살릴 수 있다.

---

코드

#include <vector>
using namespace std;

int solution(vector<int> a) {
    int answer = 0;
    int len = a.size();
    vector<int> left(len);
    vector<int> right(len);

    int MIN = a[0];
    for (int i = 0; i < len; i++) {
        if (MIN > a[i]) MIN = a[i];
        left[i] = MIN;
    }

    MIN = a[len - 1];
    for (int i = len - 1; i >= 0; i--) {
        if (MIN > a[i]) MIN = a[i];
        right[i] = MIN;
    }

    for (int i = 0; i < len; i++) {
        if (a[i] <= left[i] || a[i] <= right[i]) answer++;
    }
    return answer;
}