문제

풍선 터트리기

접근

최초 접근 방법은 최후까지 남는지 확인할 풍선이 i 번째 풍선이라면,
i 번째를 기준으로 좌,우로 나누어 확인하고자 했다.

왼쪽에서 최소값과 오른쪽에서 최소값을 구했을 때, i번째의 값이 이 3개의 값 중 가장 크다면,
무슨 수를 써도 살아남을 수 없다.
번호가 더 작은 풍선은 한번만 터트릴 수 있기 때문!
또한 가장자리의 값, 즉 가장 앞과 뒤의 값은 무조건 살아남을 수 있을 것이다.

곰곰히 생각해보니 이 방법이 맞는거 같았다.
모든 경우에도 틀리지 않는다.

그런데 문제는 시간초과가 났다.
아무래도 배열의 길이가 너무 길다보니 매번 최소값을 찾는 과정에서 시간을 너무 많이 잡아먹는다.

i를 앞에서 부터 순서대로 이동시키면서 찾아나가면, 왼쪽의 경우 따로 최소값을 찾는데 소요되는 시간은 O(1)이다.
0번째는 무조건 통과하기때문에 검사할 필요가 없으니, 1부터 시작하자.
1번째 풍선을 확인하는 방법은 0번째 풍선과 2번 이후풍선의 최소값과 비교하는 것이다.
그 후 1번 풍선과 0번 풍선을 비교하여 최소값을 가지고 있는다.

즉, a[i], min(a[:i]), min(a[i+1:]) 기존에는 이렇게 세가지의 값을 찾아주었다.
이 방법은 전체 배열을 탐색하면 결국 \(O(n^{2})\) 이 걸린다.
새로운 방법은 min(a[:i]) 에 한하여 O(1)을 보장한다.
하지만 이 방법도 결국 min(a[i+1:]) 때문에 \(O(n^{2})\) 에 근사하다..

왼쪽을 O(1)에 풀듯이 오른쪽도 하면되지 않을까? 라는 생각이 이제 들게된다.
기존의 방법으로는 두가지 모두를 O(1)에 해결할 수가 없다.

i번째 풍선일 때, 0부터 순차적으로 왔으면 왼쪽은 O(1)이지만 오른쪽은 결국 다시 봐야한다.(반대의 경우도 마찬가지)
그럼 그때그때 구하는게 아니라 미리 한바퀴돌면서 i일때 최소값을 찾아놓는다면?
이거다. DP를 써야한다.
0부터 순서대로 돌며 i이전의 최소값을 DP에 다 담아놓고, 마찬가지로 역순으로 돌며 최소값을 DP에 담는다.
이러려면 DP는 2차원으로 설계해야한다.
DP[n][2] 로 설계하면 DP[i][0] 은 0부터 i까지 중 최소값, DP[i][1]은 i부터 끝까지 값들 중 최소값을 나타낸다!
이러면 i가 살아남을 수 있을지 궁금하면 a[i], DP[i-1][0], DP[i+1][1] 세 값만 비교하면 된다!

코드

• 파이썬 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def solution(a):
    answer = 2
    size = len(a)
    dp = [[0, 0] for _ in range(size)]
    dp[0][0] = a[0]
    dp[size-1][1] = a[-1]
    for i in range(1, size-1):
        if dp[i-1][0] < a[i]:
            dp[i][0] = dp[i-1][0]
        else:
            dp[i][0] = a[i]

        if dp[size-i][1] < a[size-i-1]:
            dp[size-i-1][1] = dp[size-i][1]
        else:
            dp[size-i-1][1] = a[size-i-1]
    for i in range(1, size-1):
        if a[i] > dp[i-1][0] and a[i] > dp[i+1][1]:
            pass
        else:
            answer+=1
    return answer