[프로그래머스][C++] 풍선 터트리기

풍선 터트리기

문제 링크

풍선 터트리기

분석

다음 과정을 반복하면서 풍선 1개가 남을 때까지 터트립니다.

1. 임의의 인접한 두 풍선 중 하나를 선택하여 터트립니다.
2. 풍선을 터뜨리면 인접한 풍선끼리 다시 붙게 됩니다.

위의 과정을 반복하는 중에 번호가 더 작은 풍선을 터뜨리는 행위는 단 한번만 허용됩니다.
한 번 번호가 작은 풍선을 터뜨렸다면, 이후에는 반드시 번호가 큰 풍선만 터뜨려야합니다.

특정 풍선이 최후까지 남으려면, 해당 풍선의 왼쪽/오른쪽에서 오는 풍선들과 비교했을 때 최소값이어야 합니다.
특정 풍선 중심으로, 왼쪽이나 오른쪽에 자신보다 더 작은 풍선이 으면 안됩니다.
작은 풍선을 터트릴 수 있는 기회는 1회뿐이기 때문입니다.

각 풍선들을 1개만 남을 때까지 터트린다고 했을 때 마지막까지 남기는 것이 가능한 풍선들의 개수를 반환해야합니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> a) {
    int answer = 0;
    
    // 풍선 총 개수
    int n = a.size();
    
    // 왼쪽에서부터 현재 인덱스까지의 최소값을 저장할 배열
    vector<int> leftMin(n);
    // 오른쪽에서부터 현재 인덱스까지의 최소값을 저장할 배열
    vector<int> rightMin(n);
    
    // 왼쪽 최소값 배열 채우기
    leftMin[0] = a[0];
    for (int i = 1; i < n; ++i)
    {
        leftMin[i] = min(leftMin[i - 1], a[i]);
    }
    
    // 오른쪽 최소값 배열 채우기
    rightMin[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; --i)
    {
        rightMin[i] = min(rightMin[i + 1], a[i]);
    }
    
    // 각 풍선이 마지막까지 살아남을 수 있는지 확인한다.
    for (int i = 0; i < n; ++i)
    {
        // 풍선 a[i]가 왼쪽 최소값보다 작거나 같거나 혹은 오른쪽 최소값보다 작은 경우
        if (a[i] <= leftMin[i] || a[i] <= rightMin[i])
        {
            ++answer;
        }
    }
    
    return answer;
}

1. 왼쪽에서 오른쪽으로 탐색하면서 최소값을 저장합니다.
2. 오른쪽에서 왼쪽으로 탐색하면서 최소값을 저장합니다.
3. 어떤 풍선 a[i]가 왼쪽 최소값보다 작거나 오른쪽 최소값보다 작은 경우 끝까지 남을 수 있습니다.

성능 요약

시간 복잡도는 $O(n)$입니다.

• leftMin 배열을 채우는 반복문 $O(n)$
• rightMin 배열을 채우는 반복문 $O(n)$
• 생존 가능한 풍선 개수 세는 반복문 $O(n)$
• $O(n) + O(n) + O(n)$

공간 복잡도는 $O(n)$입니다.

• leftMin 배열 $O(n)$
• rightMin 배열 $O(n)$
• $O(n) + O(n)$

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.01MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.02ms, 4.19MB)
테스트 4 〉 통과 (0.91ms, 7.49MB)
테스트 5 〉 통과 (4.90ms, 24.6MB)
테스트 6 〉 통과 (6.90ms, 35.4MB)
테스트 7 〉 통과 (9.51ms, 46.3MB)
테스트 8 〉 통과 (9.55ms, 46.1MB)
테스트 9 〉 통과 (9.95ms, 46.3MB)
테스트 10 〉 통과 (9.57ms, 46.1MB)
테스트 11 〉 통과 (9.40ms, 46.3MB)
테스트 12 〉 통과 (12.30ms, 46.2MB)
테스트 13 〉 통과 (14.12ms, 46.3MB)
테스트 14 〉 통과 (9.85ms, 46.2MB)
테스트 15 〉 통과 (9.00ms, 46.3MB)