[Programmers] 풍선 터트리기

---

• 풍선 터트리기

---

파이썬을 사용하였습니다.

---

• 입력

  1. 일렬로 나열된 풍선들의 번호가 담긴 배열 a

• 출력

  1. 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수

• 제한사항

  1. a 의 길이는 1 이상 1,000,000 이하입니다.
  2. a의 모든 수는 서로 다릅니다수.
  3. -1,000,000,000 <= a <= 1,000,000,000

---

간단해 보이는 문제지만 시간초과가 많이 괴롭히는 문제입니다. 시간복잡도가 3n을 넘으면 시간 초과가 나는 것 같습니다.

처음에 생각했던 코드

def solution(a):
    answer = 0
    for ind, val in enumerate(a):
        if ind == 0 or ind == len(a) - 1:
            answer += 1
        else:
            leftmin = min(a[:ind])
            rightmin = min(a[ind + 1:])

            if (max(leftmin, rightmin) > val):
                answer += 1
    return answer

위의 코드로 풀면 시간 초과가 납니다. 그냥 보면 시간 복잡도가 n인 것 같지만 사실 매 순회 마다 Min() 함수를 두번씩 호출하기 때문에
사실상 2n^2과 같다고 생각해도 될 것 같습니다.

시간 초과가 나고 정말 고민을 많이 했는데 생각해보니 일정 구간은 비교대상의 숫자가 정해져 있었습니다.
잘 생각을 해보니 양쪽 끝 풍선들은 어떤 경우라도 남길 수 있고 우리가 고민해야 될 대상은 중간 풍선들인데

대상이 되는 풍선의 왼쪽 배열에서 가장 작은수, 오른쪽 배열에서 가장 작은수 두개중에 남기고 싶은 풍선의 숫자가 가장 작지만 않으면 풍선은 남을 수 있다 라는 결론이 나왔습니다.

예를 들어 9 -1 5 에서 5,9는 무슨일이 있어도 풍선을 남길 수 있고
-1 을 남기려면 (9 -1), (-1, 5) 두 그룹에서 -1이 살아남아야 합니다. 이 떄 풍선은 자기보다 작은 숫자를 터트리는걸 한번 허용해 주기 때문에 두 그룹중 한번만 자기가 작은 숫자면 풍선을 남길 수 있습니다.

이 방법으로 왼쪽/오른쪽 비교 그룹을 만들고 두 그룹에서 한번만 살아남으면 남길 수 있는 풍선이 되는 것입니다.

(설명이 어렵네요..)

---

결론적으로

왼쪽부터 오는 배열은 [-16, -16, -16, -16, -16, -92, -92, -92, -92, -92] 로 고정이 되고

오른쪽부터 오는 배열은 [-92, -92, -92, -92, -92, -92, -71, -68, -61, -33]로 고정이 됩니다.

그럼 이 배열을 가지고 인덱스에 해당하는 타겟 넘버만 비교하면 됩니다.
즉 왼쪽 배열 만들때 1n 오른쪽 배열 만들 떄 1n 마지막에 비교 할때 1n
합 3n의 시간 복잡도를 나타내기 때문에 시간 초과를 피할 수 있습니다.

---

정답 코드

def solution(a):
    answer = 0
    leftArray,left =[0 for i in a],9999999999999
    rightArray,right =[0 for i in a],9999999999999

    for ind,val in enumerate(a):
        if left > val:
            left = val
        leftArray[ind] = left

    for i in range(len(a)-1,-1,-1):
        if right > a[i]:
            right = a[i]
        rightArray[i] = right

    for ind,val in enumerate(a):
        if rightArray[ind] >= val or leftArray[ind] >= val:
            answer += 1

    return answer