[프로그래머스][월간 코드 챌린지 시즌 1][C++] 풍선 터트리기

문제

프로그래머스 월간 코드 챌린지 시즌 1 - 풍선 터트리기 (Level 3)

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

 

---

문제 풀이

접근 방식

이 문제는 프로그래머스 월간 코드 챌린지 시즌 1 3번 문제로,

아래의 규칙대로 풍선을 1개만 남을 때까지 터트렸을 때, 최후까지 남기는 것이 가능한 풍선의 개수를 구하는 문제이다.

 

풍선을 터트리는 규칙

한 풍선의 양 옆의 풍선들을 숫자가 큰 풍선 먼저 터트려 하나씩만 남기면,

양 옆에는 각각 가장 작은 번호의 풍선만 남게 된다.

그 상태에서 기준이 되는 풍선과 양 옆의 풍선의 숫자를 비교하여

기준이 되는 풍선의 숫자보다 더 큰 값이 하나라도 존재한다면,

번호가 더 작은 풍선을 터트리는 행위가 1번 가능하기 때문에 기준이 되는 풍선을 최후까지 남길 수 있다.

 

예를 들어, 7 - 6 - 4가 최종적으로 남아 있다면 6보다 큰 7은 먼저 터트릴 수 있고,

번호가 작은 4번 풍선도 1번은 제거 가능해서 6을 최후까지 남기는 것이 가능하다.

하지만, 3 - 6 - 4가 최종적으로 남아 있다면 더 작은 번호를 2번 터트려야 가능해서 규칙에 위배된다.

 

즉, 양쪽의 최솟값을 알면 최후까지 남길 수 있는지를 판단할 수 있기 때문에

left 벡터에는 처음 지점부터 끝 지점까지 탐색하며 최솟값을 저장해주었고,

right 벡터에는 끝 지점부터 처음 위치까지 탐색하며 최솟값을 저장해주었다.

그 후, for문으로 a[i]의 값과 left[i]의 값, right[i]의 값을 비교하여

a[i]보다 크거나 같은 값이 하나라도 존재하면 answer을 증가시켜 답을 구해주었다.

 

---

풀이 코드 - C++

#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;
}

실행 결과

실행 결과 : 100.0