풍선 터트리기(선형 탐색)

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

프로그래머스

 

인접한 두 풍선 중 하나를 터트릴때 작은 풍선을 터트리는 행위는 단 한 번만 할 수 있음에 유의하여야 한다.

 

풍선들의 값들은 모두 다르다고 하였으므로 풍선 중에는 최솟값인 풍선이 존재할 것이고

해당 풍선은 무조건 모든 풍선을 터트릴 수 있을 것이다.

 

그리고 다른 풍선의 관점으로는 최솟값인 풍선과 만났을때 작은 풍선을 터트려야 하므로

최솟값인 풍선을 만나기 전에는 큰 풍선만 터트리는 행위만 하여야 한다.

 

이러한 조건을 생각해보면 최솟값인 풍선과 특정 풍선을 두고 다음과 같은 구간으로 나눌 수 있다.

A의 우측 구간은 최솟값이 모든 풍선을 터트리고 남게 된다.

A는 최솟값인 풍선을 만났을때만 작은 풍선을 터트리는 행위를 해야한다.

A의 좌측 구간에서 A가 살아남으려면 A가 해당 구간의 최솟값이어야 한다.

 

이러한 방법을 사용하여 배열의 양쪽 끝단에서 최솟값 방향으로 구간을 늘려가면서

해당 구간의 최솟값이 갱신될때 해당 풍선은 살아남을 수 있다고 볼 수 있다.

물론 최솟값도 살아남을 수 있는 풍선에 포함이 된다.

 

#include <string>
#include <vector>
using namespace std;

int solution(vector<int> a)
{
    int min_index = 0;
    int min_ballon = 1000000001;
    int vec_size = a.size();
    for (int i = 0; i < vec_size; i++)
    {
        if (a[i] < min_ballon)
        {
            min_index = i;
            min_ballon = a[i];
        }
    }
    int answer = 1;
    int smallest = 1000000001;
    for (int i = 0; i < min_index; i++)
    {
        if (a[i] < smallest)
        {
            smallest = a[i];
            ++answer;
        }
    }
    smallest = 1000000001;
    for (int i = vec_size - 1; i > min_index; i--)
    {
        if (a[i] < smallest)
        {
            smallest = a[i];
            ++answer;
        }
        else break;
    }
    return answer;
}