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

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

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

---

 

-풀이-

먼저 a의 길이를 보았을때 ,O(N*N)은 불통과할게 뻔해보이므로 O(NlogN) 이나 O(N)으로 풀 수 있는 방법이 있는지 생각해보았다.

그러자 전체 개수에서 안되는 개수를 빼면 되는데, 안되는 경우를 생각해보니

해당 i번째 인덱스 원소 기준 좌측의 최솟값보다 크고, 우측의 최솟값보다 크면 안된다.

 

문제에서 주어진 "인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다" 를 마지막에 적용을 시킨다고 해보자. 

 

i번째 인덱스의 값을 5라고 하고,

좌측에서 마지막까지 살아남은 수(최솟값)을 -5라하고, 우측에서 마지막까지 살아남은 수(최솟값)을 -10이라 하자. 

이런 경우가 된다면,

1) -5와 5중 작은 번호를 터트리면 5가 살아남고, 5와 -10이 있으면 -10이 살아남으니 x

2) -5와 5중 큰번호를 터트려버리면 5가 살지 못하므로 x

3) 5와 -10중 작은 번호를 터트리면 5가 살아남고, -5와 5가 있으면 -5가 살아남으니 x

4) 5와 -10중 큰번호를 터트려버리면 5가 살지 못하므로 x

 

따라서 이런경우는 절대 살아남지 못한다.

 

그래서 처음 O(N)시간을 투자하여 i번째기준 좌측의 최솟값과, 우측의 최솟값을 저장해둔뒤, 배열을 돌며 위의 해당하는 경우를 빼주면 답이 나온다.

 

-시간 복잡도-

처음 좌,우측의 최솟값을 저장하는 로직은 O(N)이 걸리고, 풍선의 생존여부를 결정하는 로직도 O(N)이 되므로,

최종적으로O(N)이 된다.

 

-코드-

 

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

int solution(vector<int> a) {
    int answer = 0;
    int n=a.size();
    answer=n;
    vector<int> left(n),right(n);
    
    //O(N);
    left[0]=a[0];
    right[n-1]=a[n-1];
    for(int i=1;i<n;i++){
        left[i]=min(left[i-1],a[i]);
        right[n-i-1]=min(right[n-i],a[n-i]);
    }
    
    for(int i=1;i<n-1;i++){
        if(left[i]<a[i]&&right[i]<a[i]) answer--;
    }

    return answer;
}

/*
안되는 경우 = 왼쪽편의 최솟값과 오른쪽편의 최솟값 두개보다 큰경우
*/