풍선 터트리기 (68646번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 풍선 터트리기 (68646번)

난이도 : Lv 3

Time Complexity : O( N )

 

---

월간 코드 챌린지 시즌1 기출문제이다.

 

def solution(a):
    n = len(a)
    if n <= 2:
        return n
    lmin = a[:]
    rmin = a[:]
    for i in range(1, n):
        if lmin[i-1] < lmin[i]:
            lmin[i] = lmin[i-1]
        if rmin[~(i-1)] < rmin[~i]:
            rmin[~i] = rmin[~(i-1)]     
    return sum(0 if a[i] > rmin[i+1] and a[i] > lmin[i-1] else 1 for i in range(1, n-1)) + 2

 

 

★ 문제 입출력 예

[-16, 27, 65, -2, 58, -92, -71, -68, -61, -33]

 

 

위 예제의 4번 인덱스에 있는, 58 값을 가진 풍선을 기준으로 살펴보자.

 

58 풍선의 왼쪽에 더 작은 값의 풍선이 있다면,

적어도 한 번은 더 작은 풍선을 터트려야 한다.

 

마찬가지로 58 풍선의 오른쪽에 더 작은 값의 풍선이 있다면,

적어도 한 번은 더 작은 풍선을 터트려야 한다.

 

더 작은 풍선을 터뜨릴 기회는 딱 한 번만 주어지기 때문에,

58 풍선의 왼쪽과 오른쪽 모두에 더 작은 값의 풍선이 있다면

마지막에 58 풍선만 남기는 것은 불가능하다.

 

위의 사실을 활용하면, O(N)의 시간복잡도로 문제를 해결할 수 있다.

 

---

 

① rmin과 lmin 리스트를 만든다.

lmin = a[:]
rmin = a[:]
for i in range(1, n):
    if lmin[i-1] < lmin[i]:
        lmin[i] = lmin[i-1]
    if rmin[~(i-1)] < rmin[~i]:
        rmin[~i] = rmin[~(i-1)]

 

i번째 index에서, rmin[i+1] 은 i번째 풍선보다 오른쪽에 있는 풍선 중 가장 작은 풍선의 값을 나타낸다.

i번째 index에서, lmin[i-1] 은 i번째 풍선보다 왼쪽에 있는 풍선 중 가장 작은 풍선의 값을 나타낸다.

 

lmin = [-16, -16, -16, -16, -16, -92, -92, -92, -92, -92]
rmin = [-92, -92, -92, -92, -92, -92, -71, -68, -61, -33]

 

 

② 1 ~ len(a)-2 사이 index 값에 i 대해,

a[i] 가 lmin[i-1] 보다 크고, 동시에 rmin[i+1] 보다 크다면

해당 풍선 a[i] 는 마지막에 남기는 것이 불가능하다.

if a[i] > rmin[i+1] and a[i] > lmin[i-1]

 

위의 경우를 제외하면 모두 마지막에 남기는 것이 가능하므로,

가능한 풍선의 갯수를 구한다.

sum(0 if a[i] > rmin[i+1] and a[i] > lmin[i-1] else 1 for i in range(1, n-1))

 

0 번과 len(a)-1 번 index의 풍선은 한 쪽에만 다른 풍선들이 있으므로,

마지막에 남기는 것이 항상 가능하다.

따라서 위에서 계산한 값에 2를 더해서 반환해주면 정답이 된다.

return sum(0 if a[i] > rmin[i+1] and a[i] > lmin[i-1] else 1 for i in range(1, n-1)) + 2