Programmers - 풍선 터트리기

---

title: Programmers - 풍선 터트리기
date: 2022-08-12
tags:

• Algorithm

---

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

문제 요약

풍선이 나열되어 있으며, 인접한 두 풍선을 터트려 한 개의 풍선만 남긴다.
단 한 번만 번호가 작은 풍선을 터트릴 수 있으며, 그 외에는 전부 번호가 큰 풍선만 터트린다.
최후까지 남길 수 있는 풍선의 수를 return한다.

문제 풀이

처음에는 잘못된 풀이를 작성하여 약간 헤맸다.
특정 위치 기준으로 좌측은 내림차순으로 존재해야 우측에 무엇이 오든 터트릴 수 있으며, 우측은 오름차순으로 존재해야 좌측에 무엇이 와도 터트릴 수 있다고 생각하였다.
이 풀이의 문제는 간단하다. 좌우측 모두 조건에 맞지 않더라도, 좌우의 모든 풍선을 큰 번호만 터트릴 때 남는 두 개의 풍선 중 하나라도 현재 위치보다 크면 최후까지 남길 수 있다.
결국 각 위치를 기준으로 좌측, 우측에 최종적으로 남는 가장 작은 풍선의 수를 구한 뒤, 두 풍선 중 하나라도 현재 위치보다 크면 최후까지 남길 수 있는 것이다.


풍선의 개수가 2개 이하라면 모두 최후까지 남길 수 있으므로 해당 개수를 return한다.
앞에서부터 순차적으로 순회하며 좌측의 최소값을 갱신, 그 값을 vLeftMin에 차례대로 넣는다.
우측의 최소값 또한 동일하게 뒤에서부터 순차적으로 순회한다.
양 끝 풍선은 언제나 남길 수 있기에, 그 사이에 있는 풍선들을 대상으로 좌우의 풍선과 비교하여 더 큰 풍선이 존재하면 정답을 1씩 증가시킨다.

프로그램

#include <vector>

using std :: vector ;

int solution ( vector < int > a )
{
    int answer = 2 ;
    int iSize = a.size () ;
    vector < int > vLeftMin ( iSize , 1000000000 ) ;
    vector < int > vRightMin ( iSize , 1000000000 ) ;
    int * ipBallon = a.data () ;
    int iTemp = ipBallon [ 0 ] ;



    if ( iSize <= 2 )
        return iSize ;

    for ( int i = 1 ; i < iSize ; ++i )                // Find left min number
    {
        if ( iTemp > ipBallon [ i - 1 ] )
            iTemp = ipBallon [ i - 1 ] ;
        vLeftMin [ i ] = iTemp ;
    }
    iTemp = ipBallon [ iSize - 1 ] ;
    for ( int i = iSize - 2 ; i >= 0 ; --i )        // Find right min number
    {
        if ( ipBallon [ i + 1 ] < iTemp )
            iTemp = ipBallon [ i + 1 ] ;
        vRightMin [ i ] = iTemp ;
    }

    for ( int i = 1 ; i < iSize - 1 ; ++i )
    {
        if ( ( vLeftMin [ i ] < ipBallon [ i ] ) && ( vRightMin [ i ] < ipBallon [ i ] ) )
            continue ;

        ++ answer ;
    }


    return answer ;
}