문제 요약
일렬로 나열된 풍선들이 있고, 각 풍선에는 서로 다른 숫자가 적혀 있다.
풍선을 터트릴 때는 인접한 두 풍선 중 하나를 선택해 터트릴 수 있다.
단, 더 작은 번호의 풍선을 터트리는 행동은 전체 과정에서 최대 1번만 가능하다.
이 규칙을 지키면서 마지막까지 남을 수 있는 풍선의 개수를 구해야 한다.
핵심 아이디어
어떤 풍선 a[i]가 마지막까지 남을 수 있는지 판단해보자.
중요한 조건은 다음과 같다.
a[i]의 왼쪽에도a[i]보다 작은 풍선이 있고, 오른쪽에도a[i]보다 작은 풍선이 있다면a[i]는 마지막까지 남을 수 없다.
왜냐하면 왼쪽에 있는 작은 풍선과 오른쪽에 있는 작은 풍선을 모두 제거해야 a[i]가 마지막까지 남을 수 있는데, 작은 풍선을 제거하는 행동은 최대 1번만 가능하기 때문이다.
반대로 다음 중 하나라도 만족하면 해당 풍선은 마지막까지 남을 수 있다.
- 왼쪽에 자신보다 작은 풍선이 없다.
- 오른쪽에 자신보다 작은 풍선이 없다.
즉, 각 위치에서 왼쪽 최솟값과 오른쪽 최솟값만 알면 된다.
풀이 과정
1. 왼쪽 최솟값 구하기
left_min[i]를 0번 인덱스부터 i번 인덱스까지의 최솟값이라고 하자.
left_min[i] = min(a[0], a[1], ..., a[i])만약 a[i]가 left_min[i]와 같다면, a[i]의 왼쪽에는 자신보다 작은 풍선이 없다는 뜻이다.
2. 오른쪽 최솟값 구하기
right_min[i]를 i번 인덱스부터 마지막 인덱스까지의 최솟값이라고 하자.
right_min[i] = min(a[i], a[i + 1], ..., a[n - 1])만약 a[i]가 right_min[i]와 같다면, a[i]의 오른쪽에는 자신보다 작은 풍선이 없다는 뜻이다.
3. 살아남을 수 있는 풍선 판단하기
각 풍선 a[i]에 대해 다음 조건을 확인한다.
a[i] == left_min[i] or a[i] == right_min[i]이 조건을 만족하면 해당 풍선은 마지막까지 남을 수 있다.
모든 숫자는 서로 다르므로 == 비교를 사용할 수 있다.
Python 코드
def solution(a):
n = len(a)
if n <= 2:
return n
left_min = [0] * n
right_min = [0] * n
left_min[0] = a[0]
for i in range(1, n):
left_min[i] = min(left_min[i - 1], a[i])
right_min[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
right_min[i] = min(right_min[i + 1], a[i])
answer = 0
for i in range(n):
if a[i] == left_min[i] or a[i] == right_min[i]:
answer += 1
return answer코드 설명
left_min
왼쪽에서부터 현재 위치까지의 최솟값을 저장한다.
left_min[i] = min(left_min[i - 1], a[i])현재 풍선이 left_min[i]라면, 현재 풍선보다 작은 값이 왼쪽에 없다는 뜻이다.
right_min
오른쪽에서부터 현재 위치까지의 최솟값을 저장한다.
right_min[i] = min(right_min[i + 1], a[i])현재 풍선이 right_min[i]라면, 현재 풍선보다 작은 값이 오른쪽에 없다는 뜻이다.
생존 가능 조건
if a[i] == left_min[i] or a[i] == right_min[i]:
answer += 1왼쪽 또는 오른쪽 중 한쪽에 자신보다 작은 풍선이 없다면 마지막까지 남길 수 있다.
반대로 양쪽 모두에 자신보다 작은 풍선이 있다면, 작은 풍선을 두 번 제거해야 하므로 조건을 만족할 수 없다.
공간 최적화 코드
위 풀이는 이해하기 쉽지만, left_min, right_min 배열을 모두 사용하므로 공간 복잡도가 O(n)이다.
조금 더 최적화하면 왼쪽에서 보이는 최솟값 후보와 오른쪽에서 보이는 최솟값 후보를 set에 담아 해결할 수도 있다.
def solution(a):
answer = set()
left = float('inf')
for i in range(len(a)):
if a[i] < left:
left = a[i]
answer.add(i)
right = float('inf')
for i in range(len(a) - 1, -1, -1):
if a[i] < right:
right = a[i]
answer.add(i)
return len(answer)이 방식도 같은 원리다.
- 왼쪽에서 봤을 때 최솟값이 되는 풍선
- 오른쪽에서 봤을 때 최솟값이 되는 풍선
이 두 종류의 풍선은 마지막까지 남을 수 있다.
시간 복잡도
배열을 왼쪽에서 한 번, 오른쪽에서 한 번 순회한다.
O(n)a의 길이가 최대 1,000,000이므로 정렬이나 완전 탐색은 사용할 수 없다.
이 문제는 반드시 선형 시간에 해결해야 한다.
정리
이 문제는 실제로 풍선을 터트리는 과정을 시뮬레이션하면 어렵다.
하지만 어떤 풍선이 살아남을 수 없는 경우를 생각하면 조건이 단순해진다.
왼쪽에도 더 작은 값이 있고,
오른쪽에도 더 작은 값이 있으면 생존 불가능따라서 각 위치 기준 왼쪽 최솟값과 오른쪽 최솟값만 구하면 O(n)에 해결할 수 있다.
