[Algorithm] Programmers :: 풍선 터트리기

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

프로그래머스

int solution(vector<int> a)
{
    if (a.size() <= 2) return a.size();
    
    int answer = 2;
    int minIndex = 0;
    int minValue = 0x3f3f3f3f;
 
    for (int i = 0; i < a.size(); ++i)
    {
        if (a[i] < minValue)
        {
            minValue = a[i];
            minIndex = i;
        }
    }
 
    minValue = a[0];
    for (int i = 1; i < minIndex; ++i)
    {
        if (a[i] < minValue) 
        {
            minValue = a[i];
            ++answer;
        }
    }
 
    minValue = a[a.size() - 1];
    for (int i = a.size() - 2; i > minIndex; --i)
    {
        if (a[i] < minValue) 
        {
            minValue = a[i];
            ++answer;
        }
    }
 
    if (minIndex == 0 || minIndex == a.size() - 1) return answer;
    else return answer + 1;
}

탐색..으로는 최대크기가 100만이라 당연히 안되고, 1시간가량 고민하다 접근법에 대해서 다른분의 글을 통해 쉽게 이해할 수 있었습니다.

 

https://school.programmers.co.kr/questions/43693

프로그래머스

 

이해만하면 코드작성은 위의 코드처럼 쉽습니다.

 

기준이 되는 값이 가장작은값의 왼쪽에 위치해있다고 가정했을 때, 기준이되는값은 자신의 왼쪽에있는 값들만 처리하면 살아남을 수 있습니다.

왜냐하면 자신의 왼쪽에 있는 것들을 제외한 나머지값들, 즉 자신과 가장작은값 사이에있는것들과 가장작은값 오른쪽에 있는것들은 가장작은값이 전부 터트려버리는게 가능하기 때문입니다.

 

그렇게 가장작은값을 이용해서 다 터트려버린 후, 딱 한번의 기회만 있는 '더 작은값을 터트리기'를 이용해서 가장 작은값을 터트려버리면 자신은 살아남을 수 있습니다.

 

그렇다면 자신의 왼쪽에 있는것들을 다 터트릴 수 있는지 확인해야하는데, 자신의 왼쪽에 자기보다 큰값들만 있으면 됩니다. 자기보다 큰값을 터트릴 기회는 무한이기 때문입니다. 

이런식으로 양쪽끝에서 가장작은값까지 최소값을 갱신하면서 접근하면 됩니다.

 

마지막에 answer에 +1에서 +1은 가장작은값을 의미하는것인데(가장 작은값은 항상 살아남을 수 있습니다), 만약 가장작은값이 양쪽끝에 있다면 겹치니까 +1을 하지 않습니다.