문제 풀이 아이디어
풍선 터뜨리기 프로세스
다른 풍선부터 싹 터뜨리자
조건에 의하면 인접한 풍선만 짝을 지어 터뜨릴 수 있습니다. 따라서 최후의 풍선이 되기 위해서는 다른 풍선들이 다 터지고 마지막으로 남은 풍선과 최후의 풍선이 나란히 있어야 합니다. 터진 풍선의 공간은 밀착되므로 풍선을 터뜨리는 순서는 신경을 쓸 필요가 없습니다. 어찌되었든 간에 최후의 풍선만 터뜨리지 않으면 됩니다.
그렇다면 일단 인접한 두 풍선을 고를 때, 즉 터뜨릴 두 풍선을 고를 때 최후의 풍선을 고르지 않고 진행을 합니다. 그러면 최후의 풍선이 절대 터질 일이 없겠지요? 그리고 다른 풍선을 터뜨릴 때 무조건 “번호가 큰” 풍선만을 터뜨립니다. “번호가 작은” 풍선을 터뜨릴 찬스는 단 1번 뿐이므로 최후의 풍선이 터지지 않기 위해 필요할 수 있습니다. 아껴둡시다.
Case 1) 최후의 풍선이 양 사이드에 있는 풍선인 경우
최후의 풍선이 양 사이드에 있는 케이스부터 살펴보겠습니다. 이 경우 최후의 풍선을 고르지 않고 다른 모든 풍선을 다 터뜨렸을 때 최후의 풍선 하나와 인접한 풍선이 하나가 남게 됩니다.
마지막으로 두 풍선을 고릅니다. 그리고 번호를 비교합니다. 만약 인접한 풍선이 최후의 풍선보다 번호가 크다면 그냥 터뜨리면 됩니다. 그리고 반대로 인접한 풍선이 최후의 풍선보다 번호가 작다면 아껴둔 “찬스”를 활용해서 번호가 작은 인접한 풍선을 터뜨리면 됩니다.
따라서 최후의 풍선이 양 사이드에 있는 경우 무조건 그 풍선은 마지막 까지 터지지 않을 수 있습니다.
Case 2) 최후의 풍선이 양 사이드에 있지 않은 경우
최후의 풍선이 양 사이드에 있지 않은 경우에는 다른 모든 풍선을 터뜨린 경우 3개의 풍선이 남게 됩니다. 바로 최후의 풍선 왼쪽에서 다 터뜨리고 남은 풍선, 최후의 풍선, 최후의 풍선 오른쪽에서 다 터뜨리고 남은 풍선입니다. 이렇게 3개가 남게 되면 최후의 풍선을 고르지 않고는 더 이상 풍선을 터뜨릴 수 없게 됩니다.
이렇게 3개가 남은 상황에서 최후의 풍선이 살아남을 수 있는 케이스는 뭐가 있을까요. 일단 3개의 풍선 중에서 최후의 풍선의 번호가 가장 작은 경우입니다. 이 경우에는 최후이 풍선은 찬스를 사용하지 않아도 무조건 살아남을 수 있습니다.
3개의 풍선 중에서 최후의 풍선의 번호가 중간에 위치한 경우입니다. 이 경우 번호가 작은 풍선하고 짝지어졌을 때 아껴둔 “찬스”를 1번 활용하면 최후의 풍선이 살아남을 수 있습니다.
문제는 3개의 풍선 중에 최후의 풍선의 번호가 가장 큰 경우입니다. 이 경우는 찬스는 1번 밖에 없기에 최후의 풍선은 얄짤없이 터지는 경우 밖에는 없습니다.
따라서 최후의 풍선이 살아남기 위해서는 양쪽에 남은 풍선보다 모두 크면 안됩니다.
프로세스를 코드로
위에서 설명한 프로세스와 조건을 코드를 옮겨보겠습니다. 먼저 최후의 풍선을 빼고 모든 풍선을 터뜨리는 것은 다른 풍선들 중에 가장 작은 풍선을 찾는 것입니다.
풍선이 양 사이드에 있는 경우 해당 풍선은 조건을 따져볼 필요도 없습니다. 따라서 ans 값은 2부터 시작하고 나머지 풍선들의 조건만 따져보면 됩니다.
따라서 최후의 풍선이 i번째 풍선이라고 하면 남은 3개의 풍선은 처음 ~ (i - 1)번째 풍선까지의 최솟값, i번째 풍선의 값, (i + 1) ~ 마지막 풍선까지의 최솟값입니다. 이 3개의 값을 남겨놓고 비교하면 됩니다.
시간복잡도 조건
a의 크기는 최대 1,000,000입니다. 따라서 무조건 O(N) 이내의 알고리즘을 사용해서 풀어야 합니다. 따라서 최솟값을 구하기 위해서 min() 메소드를 활용하면 안됩니다. min() 메소드는 O(N)입니다. 하지만 모든 풍선을 탐색하기 위해서 O(N)의 반복문이 필요하므로 결과적으로 O(N^2)가 되기 때문입니다.
따라서 저는 O(N)으로 왼쪽, 오른쪽에서 부터의 미리 최솟값 배열을 구해놓는 방법을 사용하겠습니다.
코드
func solution(_ a:[Int]) -> Int {
// left[i] = 0 ~ i까지의 수 중에 최솟값
var left = Array(repeating: Int.max, count: a.count)
left[0] = a[0]
for i in 1..<a.count {
left[i] = a[i] < left[i - 1] ? a[i] : left[i - 1]
}
// right[i] = i ~ (a.count - 1)까지의 수 중에 최솟값
var right = Array(repeating: Int.max, count: a.count)
right[a.count - 1] = a[a.count - 1]
for i in 2...a.count {
let index = a.count - i
right[index] = a[index] < right[index + 1] ? a[index] : right[index + 1]
}
// a[0]와 a[a.count - 1]은 무조건 최후에 터뜨릴 수 있음
var ans = 2
// 왼쪽에 위치한 풍선들의 최솟값, 오른쪽에 위치한 풍선들의 최솟값 보다 모두 크지 않으면 최후에 터뜨릴 수 있음.
for i in 1..<(a.count - 1) {
if !(a[i] > left[i - 1] && a[i] > right[i + 1]) { ans += 1 }
}
return ans
}