201002 [월간 코드 챌린지 시즌1] 9월 문제-풍선 터트리기

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

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

문제:

마지막까지 남을 수 있는 숫자의 개수를 구하는 문제입니다.

비교 했을 때 큰 값들은 무조건 제거 되고, 작은 값은 한 번만 제거 될 수 있습니다.

인접한 풍선을 터트리는데, 012가 있을 때 01이 아닌 12로 터트릴 수 있습니다. 그래서 양 끝은 무조건 남을 수 있습니다(가운데끼리 터트리고 가운데 1개가 남아서 총 3개일때는 터트리는 기준에 따라 남는 것이 달라지므로 3개 모두 최후의 풍선이 될 수 있습니다.).

다른 값들 보다 작으면 끝까지 남아서 정답 개수는 갱신 횟수입니다.

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> a) {
    int answer = 2;
    
    if(a.size() <= 2 ) return a.size();
    
    int left = a.front();
    int right = a.back();
    for(int i = 1; i < a.size()-1; i++){
        if (left > a[i]){
            answer++;
            left = a[i];
        }
        if (right > a[a.size()-1-i]){
            answer++;
            right = a[a.size()-1-i];
        }
        
    }
    if (left == right)
            answer--;
    return answer;
}

코드:

양 끝 값은 무조건 남으므로 기본 정답 값으로 2를 줬습니다.

벡터 a의 길이가 2보다 작으면 모두 살아 남으므로 a의 길이를 정답으로 리턴합니다.

left와 right는 양 끝 값에서 시작합니다.

작은 값이 살아남으므로 양 쪽에서 작은 값들을 찾아갑니다. 그리고 찾은 횟수만큼 정답을 더 해주고 값을 갱신합니다.

반복문을 탈출 했을 때 left와 right 값이 같으면 답이 중복 체크 된 것이라서 -1 해줍니다.