[Programmers] 풍선 터트리기

👀 문제 설명

문제

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

a의 길이는 1 이상 1,000,000 이하입니다.

• a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
• a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
• a의 모든 수는 서로 다릅니다.

 

입출력 예

입출력 예 설명

입출력 예 #1

• 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
• 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

입출력 예 #2

• 최후까지 남을 수 있는 풍선은 -16, -92, -71, -68, -61, -33이 써진 풍선으로 모두 6개입니다.

 

✍🏻풀이

[틀림] - 시간 초과

각 인덱스를 기준으로 왼쪽에서 제일 작은 값 (leftMin), 오른쪽에서 제일 작은 값(rightMin)을 가져오고, leftMin, rightMin, a.at(index)를 비교해서 a.at(index)가 제일 큰 값이라면 해당 값은 마지막까지 남을 수 없다.

a.at(index)가 세 값 중 최댓값이 아니라면 answer + 1 해준다.

-> 이 과정에서 각 인덱스에 접근하기 위한 for문, 그리고 그 for문 안에서 왼쪽에서 제일 작은 값, 오른쪽에서 제일 작은 값을 가져오기 위해 for문을 사용하기 때문에 이중 for문이 되어버린다.

-> 시간 초과!

 

[정답]

1. 왼쪽부터 차례대로 해당 인덱스까지의 최솟값을 구해 leftMin 배열에 넣어둔다.

2. 오른쪽부터 차례대로 해당 인덱스까지의 최솟값을 구해 rightMin 배열에 넣어둔다.

3. 0부터 a.size() - 1인덱스를 차례로 방문하며, leftMin[i], rightMin[i], a.at(i)를 비교해, a.at(i)가 최댓값이라면 continue, 아니라면 answer + 1 한다.

 

코드

//  풍선 터트리기 (https://programmers.co.kr/learn/courses/30/lessons/68646)

#include <iostream>
#include <vector>

#define MAX 1000000

using namespace std;

int leftMin[MAX];
int rightMin[MAX];

/**
 * 1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트린다.
 * 1-1. 번호가 더 큰 풍선을 터트린다.
 * 1-2. 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 가능하다.
 * 2. 빈 공간이 없도록 풍선들을 중앙으로 밀착시킨다.
 */
/**
 * [틀린 풀이]
 * 1. 각 인덱스를 기준으로 왼쪽에서 제일 작은 값, 오른쪽에서 제일 작은 값을 가져온다.
 *      -> 번호가 더 큰 풍선을 터트리면 결국 제일 작은 값이 남기 때문에
 * 2. 왼쪽에서 제일 작은 값, a.at(현재 인덱스), 오른쪽에서 제일 작은 값
 *    세 값을 비교해서, 현재 인덱스의 값이 남을 수 있는지 확인한다. (번호가 더 작은 풍선을 터트리는 행위는 1번만 가능)
 * 3. 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 가능하므로, 남은 세 값중 a.at(현재 인덱스) 값이 제일 크면 해당 인덱스는 마지막까지 남길 수 없다.
 * => 시간 초과! (이중 for문을 사용하게 된다.)
 */
/**
 * [맞는 풀이]
 * 1. 왼쪽부터 차례대로 해당 인덱스까지의 최솟값을 구해 leftMin 배열에 넣어둔다. (0부터 a.size() - 1)
 * 2. 오른쪽부터 차례대로 해당 인덱스까지의 최솟값을 구해 rightMin 배열에 넣어둔다. (a.size() - 1부터 0)
 * 3. 0부터 a.size() - 1인덱스를 차례대로 돌며, leftMin[i], rightMin[i], a.at(i)를 비교해 a.at(i)가 최댓값이라면 continue를 하고, 아니라면 answer + 1한다.
 */
int solution(vector<int> a) {
    int answer = 0;

    if (a.size() <= 3) {
        return a.size();
    }

    // 왼쪽 최솟값 저장해두기
    int minNum = a.at(0);
    for (int i = 0; i < a.size(); i++) {
        if (minNum > a.at(i)) {
            minNum = a.at(i);
        }

        leftMin[i] = minNum;
    }

    // 오른쪽 최솟값 저장해두기
    minNum = a.at(a.size() - 1);
    for (int i = a.size() - 1; i >= 0; i--) {
        if (minNum > a.at(i)) {
            minNum = a.at(i);
        }

        rightMin[i] = minNum;
    }

    for (int i = 0; i < a.size(); i++) {
        // a.at(i)가 왼쪽 최솟값, 오른쪽 최솟값, a.at(i) 중 최댓값이라면 해당 값은 끝까지 남을 수 없다.
        if (a.at(i) > leftMin[i] && a.at(i) > rightMin[i]) {
            continue;
        }

        answer++;
    }

    return answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);

    cout << solution({ 9, -1, -5 }) << "\n";
    cout << solution({ -16, 27, 65, -2, 58, -92, -71, -68, -61, -33 }) << "\n";

    return 0;
}