문제

풀이

입력의 길이가 최대 1,000,000개이므로 시간초과를 피하려면 $O(n)$ 안에 풀 방법을 찾아야 한다.

문제의 표현대로 '최후까지 남기는 것이 가능한 풍선'을 찾기 위해 a를 순회한다고 생각해 보자. a[i]를 최후까지 남길 수 있으려면 어떤 조건이 필요한가? 항상 인접한 풍선 중 큰 수를 터뜨리고, 단 한 번만 작은 풍선을 터뜨릴 수 있다. a[i]를 기준으로 왼쪽에 있는 풍선과 오른쪽에 있는 풍선을 각각 그룹으로 생각하고 항상 큰 수만 터뜨린다면 양쪽에는 최솟값만 남을 것이다. 그리고 a[i]가 두 값보다 크다면 어떻게 해도 a[i]를 살릴 수 없다. 반대로 두 값 중 적어도 하나보다는 작다면 살릴 수 있다. 하지만 모든 a[i]에 대해 좌우의 최솟값을 계속 구하려면 시간초과가 발생할 것이 뻔하므로 이 아이디어를 적용하면서 $O(n)$ 안에 풀 방법을 고민해 보았다.

언제나 최솟값을 기준으로 생각하게 되므로 배열 전체의 최솟값을 찾아서 이를 중심으로 판별하면 된다. 배열 전체의 최솟값을 a[m]이라고 한다면 배열 a[m]의 왼쪽 부분과 오른쪽 부분으로 나눌 수 있다. a[m]보다 왼쪽에 있는 값 x는 오른쪽 최솟값이 반드시 a[m]이면서 x > a[m]이므로 왼쪽 최솟값이 x보다 커야 살릴 수 있다. 즉, 왼쪽에서부터 탐색하여 누적 최솟값보다 큰 값만 살릴 수 있다. 오른쪽도 마찬가지로 오른쪽 끝에서부터 탐색하여 누적 최솟값보다 큰 값만 살릴 수 있다. 최솟값을 찾는 데 한 번, 인덱싱에 한 번, 각 풍선을 판별하는데 한 번 순회가 이루어지므로 시간복잡도는 $O(n)$이다.

코드

def solution(a):
    flag = a.index(min(a))
    answer = 1
    l = a[0]
    r = a[-1]
    for x in a[:flag]:
        if l >= x:
            answer += 1
            l = x
    for x in a[flag+1:][::-1]:
        if r >= x:
            answer += 1
            r = x
    return answer

양 끝에서부터 배열을 훑으며 누적 최솟값보다 작은 값이 나타나면 체크하고 누적 최솟값을 갱신한다. a의 모든 수가 다르다는 조건이 있으며 양 끝 값은 무조건 살릴 수 있으므로 조건은 '작거나 같음'으로 설정했다.

사족

문제 조건이 길고 복잡해서 이해하는 데 시간이 좀 걸렸는데, 알고 보니 아이디어만 생각해내면 간단하게 풀 수 있는 문제였다. 다만 효율성 테스트가 있었다면 시간초과가 났을지도 모른다.