프로그래머스 풍선 터트리기

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

프로그래머스

1. 특징

1) 구현

 

2. 조건

• 한 풍선의 양 옆의 풍선들을 숫자가 큰 풍선 먼저 터트려서 하나씩만 남기면, 양 옆에는 각각 가장 작은 번호의 풍선만 남게 된다
• 기준 풍선과 양 옆의 풍선을 비교하여, 기준이 되는 풍선의 숫자보다 더 큰 값이 하나라도 존재하면, 기준 풍선은 최후까지 남길 수 있다. 
• 예를들어
  • 7 6 4가 최종적으로 남은 경우 6보다 큰 값이 7 하나이므로, 6은 최후까지 남는다
  • 3 6 4가 최종적으로 남은 경우 6보다 큰 값이 하나도 없기 때문에, 6은 최후까지 남지 않는다

3. 구현 방식

• l[i] : 0 ~ i-1까지의 최솟값을 저장하는 배열 생성
• r[i]: n-1 ~ i+1까지의 최솟값을 저장하는 배열 생성
• cur < l[i] || cur < r[i] 이면, 정답++

 

4. 코드

#include <bits/stdc++.h>

using namespace std;

int l[1000002]; //l[i]: 0 ~ i-1까지의 최솟값
int r[1000002]; //r[i]: n-1 ~ i+1까지의 최솟값
int solution(vector<int> a) 
{
    int n = a.size();
    
    if(n==1) return 1; 
    if(n==2) return 2;
    int answer = 2;
    
    int mn = a[0];
    l[0] = a[0];
    
    //-16    27    65   -2    58    -92   -71    -68    -61    -33
    //      -16   -16   -16   -16   -16   -92    -92    -92 
    for(int i = 1; i < a.size() - 1; i++) // 배열의 양쪽 끝값은 빼주고 순회
    {
        int cur = a[i];
        if(cur < mn) 
        {
            l[i] = mn;
            mn = cur;
        }
        else
        {
            l[i] = mn;
        }
    }    
    
    mn = a[n-1];
    r[n-1] = a[n-1];
    
    //-16    27    65   -2     58    -92   -71    -68    -61    -33
    //      -92   -92   -92   -92    -33   -33    -33    -33
    
    for(int i = a.size() - 2; i >= 0; i--)
    {
        int cur = a[i];
        if(cur < mn)
        {
            r[i] = mn;
            mn = cur;
        }
        else
        {
            r[i] = mn;
        }
    } 
    
    
    for(int i = 1; i < n-1; i++)
    {
        int cur = a[i];
        if(cur < l[i] || cur < r[i]) answer++;        
    }
    
    // for(int i = 1; i < n-1; i ++)
    // {
    //     cout << a[i] << ' ';
    // }    
    // cout << endl;
    // for(int i = 1; i < n-1; i ++)
    // {
    //     cout << l[i] << ' ';
    // }    
    // cout << endl;
    // for(int i = 1; i < n-1; i ++)
    // {
    //     cout << r[i] << ' ';
    // }
    
    return answer;
}