문제 푼 날짜 : 2021-05-05

문제

링크 : [https://programmers.co.kr/learn/courses/30/lessons/68646]

접근 및 풀이

각각의 풍선이 마지막까지 남을 수 있는 조건을 떠올리는 것이 핵심이라고 생각했다.
문제에서 주어진 조건 중, 작은 값을 터트릴 수 있는 기회가 단 한 번뿐이기 때문에 이 기회는 마지막 풍선이 남게 하기 위해 사용하여야 한다고 생각했고, 그 외에 풍선을 터트릴 때는 무조건 큰 풍선을 터트리도록 했다.
이렇게 풍선들을 터트려나갔을 때, 임의의 풍선이 마지막까지 남기 위해서는 마지막 순간(풍선이 3개 남았을 때)의 양옆의 풍선들의 숫자 상태가 중요하다.
만약 남기고 싶은 풍선이 B이고, B의 양 옆 풍선이 A, B일 경우 B가 남을 수 있는 경우의 수를 찾아보았다. (A, B, C 순으로 나열되어 있을 경우에 대해서 생각해보았다.)

1. A < B < C or A > B > C

가능하다. 아직 작은 값을 터트릴 수 있는 기회가 남았기 때문에 B보다 큰 값을 터트리고 난 후에 B보다 작은 값을 터트린다면 B는 마지막까지 남을 수 있다.

2. A > B and C > B

가능하다. 이 때는 작은 값을 터트리는 기회를 사용할 필요도 없이, B보다 큰 값들을 터트리면 B는 마지막까지 남을 수 있다.

3. A < B and C < B

불가능하다. 작은 값을 터트릴 기회를 통해 B보다 작은 풍선을 터트리더라도, B보다 작은 풍선이 하나 더 남아서 반드시 B를 터트려야하기 때문이다.

위의 경우의 수를 모두 따져봤을 때, 마지막으로 남기고 싶은 풍선의 값이 양 옆의 풍선의 값 둘 중에 최소 하나보다만 작으면 마지막까지 남을 수 있다고 생각하였다.

떠올린 아이디어를 구현하기 위해서 풍선 값들이 저장된 벡터의 가장 왼쪽 인덱스와 가장 오른쪽 인덱스에서 각각 시작하여 각 인덱스까지 최솟값이 얼마인지를 저장한 후에 각 풍선마다 마지막까지 남을 수 있는지 체크해주었다. 이렇게 구현하면 시간복잡도는 O(n)이다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> a) {
    int answer = 0;
    int len = a.size();
    vector<int> fromLeft(len);
    vector<int> fromRight(len);
    
    int MIN = a[0];
    for (int i = 0; i < len; i++) { // 왼쪽부터 각 인덱스까지의 최솟값 저장
        fromLeft[i] = MIN = (MIN > a[i] ? a[i] : MIN);
    }
    
    MIN = a[a.size() - 1];
    for (int i = len - 1; i >= 0; i--) { // 오른쪽부터 각 인덱스까지의 최솟값 저장
        fromRight[i] = MIN = (MIN > a[i] ? a[i] : MIN);
    }
    
    for (int i = 0; i < len; i++) { // 왼쪽, 오른쪽에서의 최솟값과 비교
        if (a[i] <= fromLeft[i] || a[i] <= fromRight[i]) answer++;
    }
    
    return answer;
}

결과

피드백

처음엔 그냥 무식하게 풀어보자는 생각으로 풍선들을 직접 터트려가면서 답을 찾으려했고, 그리디하게 문제를 해결하려다가 잘되지 않았다.
대회라고 생각하고 문제를 풀었는데, 30분 정도가 지나도록 해결하지 못했기 때문에 틀린문제라 생각한다.
좀 더 문제를 많이, 다양하게 풀어봐야할 것 같다. 풀고나서도 다른 분들의 포스팅도 많이 참고해서 다양한 접근법을 익혀야겠다고 생각했다.