[C++로 풀이] 풍선 터트리기⭐⭐⭐

📌 풍선 터트리기

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

역시 시간 복잡도를 생각해야 한다. a의 길이가 무려 1,000,000 이기 때문이다!

• 임의의 인접한 두 풍선 중 더 큰 번호의 풍선을 터뜨리는 것은 제약이 없다.
  • 최소값을 가진 풍선의 양옆 인접한 풍선들은 모두 제거될 수 있다.
• 임의의 인접한 두 풍선 중 더 작은 번호의 풍선을 터뜨리는 것은 딱 한번만 가능하다.
  • 따라서 최소값을 가진 풍선은 더 작은 번호의 풍선을 터뜨리는 한번의 찬스를 사용할 필요 없이 무조건 최후까지 살아 남는 것이 가능하다.
  • 그러나 최소값이 아닌 풍선들이 자신이 최후까지 살아남을 수 있는 풍선인지를 알기 위해선
    • 👉 더 작은 번호의 풍선을 제거할 수 있는 한번의 찬스는 “자기 자신과 최소값 풍선 사이에서 최소값 풍선을 제거할 때” 사용되어야 한다.
    • 👉 따라서 자신이 최후까지 살아남기 위해선, 최소값 풍선이 제거시켜줄 수 없는 곳에 자신보다 작은 풍선이 인접해있으면 안된다.

여담으로 주의할 사항은 a를 “정렬”시키면 절대 안된다. 저 순서대로 풍선이 놓여져있다는 것이기 때문에 이 풍선들의 순서를 문제에서 주어진대로 유지해야 하며 정렬 시키면 안된다!! (내가 처음에 그랬었다..😅 정렬시키면 당연히 모든 풍선이 최후까지 남는게 가능해진다.)

[-16, 27, 65, 2, 58, -92, -71, -68, -61, -33]

• 예를 들어 두 번째 예제에서 (두번째 예제의 a 최소값은 -92 이다.)
• 65가 최후까지 살아남는 것이 가능한지를 따져보려면
  • 밑줄 친 부분들은 최소값인 -92 를 만났을 떄 제거될 수 있다. -92와 65를 제외한 곳에서 밑줄 쳐지지 않은 부분은 -92가 제거할 수 없는 부분이다. 65가 가로막고 있어 인접하지 않은 부분이다. 그리고 65가 -92 를 제거하는데 더 작은 것을 제거할 수 있는 딱 한번의 찬스를 쓰게 된다.
    • [-16, 27, ✨65, -2, 58, -92, -71, -68, -61, -33]
  • [-16, 26, ✨65] 그러나 -92로 제거할 수 없는 범위에 65보다 작은 -16, 27 이 존재한다. 65는 이미 최소값 -92를 제거할 때 찬스를 썼으므로 이들을 제거할 수 없다. 👉 따라서 65는 최후까지 살아남을 수 없다.
• -61이 최후까지 살아남는 것이 가능한지를 따져보려면
  • 밑줄 친 부분들은 최소값인 -92 를 만났을 떄 제거될 수 있다. -92와 -61를 제외한 곳에서 밑줄 쳐지지 않은 부분은 -92가 제거할 수 없는 부분이다. -61가 가로막고 있어 인접하지 않은 부분이다. 그리고 -61가 -92 를 제거하는데 더 작은 것을 제거할 수 있는 딱 한번의 찬스를 쓰게 된다.
    • [-16, 27, 65, -2, 58, -92, -71, -68, ✨-61, -33]
  • [✨-61, -33] -33은 -61보다 더 크므로 찬스없이 제거될 수 있다. 👉 따라서 -61은 최후까지 살아남을 수 있다.

✈ 1 차 풀이 (⏰시간 초과)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> a) {
    int answer = 0;
    int minIndex = min_element(a.begin(), a.end()) - a.begin(); // 최소값 인덱스
    
    for(int i = 0; i < a.size(); i++){ // 모든 풍선들 순회하면서 최후까지 살아남을 수 있는 풍선인지 검사 후 카운팅해야 함
        bool flag = true;
        
        if (i < minIndex){  // 현재 풍선이 최소값 보다 왼쪽에 있는 풍선일 때
            for(int j = 0; j < i; j++){ // 현재 풍선보다 왼쪽 (최소값이 제거해줄 수 없는 공간)에 
                if (a[j] < a[i]){ // 현재 풍선보다 작은 풍선이 있다면 👉 현재 풍선은 최후까지 살아남을 수 없는 풍선!
                    flag = false;
                    break;
                }
            }
        }
        if (i > minIndex){  // 현재 풍선이 최소값 보다 오른쪽에 있는 풍선일 때
            for(int j = i + 1; j < a.size(); j++){ // 현재 풍선보다 오른쪽 (최소값이 제거해줄 수 없는 공간)에 
                if (a[j] < a[i]){  // 현재 풍선보다 작은 풍선이 있다면 👉 현재 풍선은 최후까지 살아남을 수 없는 풍선!
                    flag = false;
                    break;
                }
            }
        }
        
        if(flag) answer++; // 위 검사에 모두 걸리지 않은 경우에만 카운팅.
        // i == minIndex 최소값 풍선의 경우는 무조건 이 경우에 걸려서 카운팅 됨.
    }
    
    return answer;
}

for(int j = 0; j < i; j++) 이 정도만 이중 for문 돌리는 것도 시간초과가 나는구나! ㅠㅠ

• 현재 풍선이 최소값 풍선보다 왼쪽에 있다면 👉 현재 풍선의 왼쪽 범위에 더 작은 값이 있다면 살아남기 불가능한 풍선
• 현재 풍선이 최소값 풍선보다 오른쪽에 있다면 👉 현재 풍선의 오른쪽 범위에 더 작은 값이 있다면 살아남기 불가능한 풍선

그러니 각각 왼쪽 범위, 오른쪽 범위를 굳이 순회하며 더 작은 값 있는지 찾을 필요 없이! 왼쪽 범위와 오른쪽 범위 각각의 "최소값"과의 비교만 해보면 된다. 이걸 바탕으로 고친 풀이가 아래 풀이이다.

✈ 2 차 풀이 ⭕

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> a) {
    int answer = 1; // 👉 최소값 풍선은 무조건 살아남을 수 있다! 최소값 포함하기 위해 answer을 1 로 초기화
    int minIndex = min_element(a.begin(), a.end()) - a.begin();
    int tempMin = 1000000000;
    
    for(int i = 0; i < minIndex; i++){  // 최소값 풍선보다 왼쪽 범위
        if (tempMin > a[i]){ // 왼쪽부터 쭉 업뎃해온 최소값이 현재의 풍선이 더 크다면 👉 현재의 풍선은 자신의 왼쪽에 있는 풍선들보다 작다는 것이므로 문제 없다. 
            tempMin = a[i]; // 최소값 업뎃
            answer++; // 최후까지 살아남을 수 있는 풍선입니다~
        }
    }
    
    tempMin = 1000000000; 
    for(int i = a.size() - 1; i > minIndex; i--){ // 최소값 풍선보다 오른쪽 범위
        if (tempMin > a[i]){ // 오른쪽부터 쭉 업뎃해온 최소값이 현재의 풍선이 더 크다면 👉 현재의 풍선은 자신의 오른쪽에 있는 풍선들보다 작다는 것이므로 문제 없다. 
            tempMin = a[i]; // 최소값 업뎃
            answer++; // 최후까지 살아남을 수 있는 풍선입니다~
        }
    }
    
    return answer;
}

이렇게 풀면 O(N) 시간 복잡도를 보장할 수 있다.

[-16, 27, 65, 2, 58, -92, -71, -68, -61, -33]

• 2가 최후까지 살아남을 수 있는 풍선인지를 검사할 땐 tempMin은 -16 인 상태일 것이다. 2 > -16 이므로 2번 풍선은 최후까지 살아남을 수 없다.
• -68이 최후까지 살아남을 수 있는 풍선인지를 검사할 땐 tempMin은 -61 인 상태일 것이다. -68 < -61 이므로 -68번 풍선은 자신의 오른쪽 범위보다 더 작다는 것이므로 최후까지 살아남을 수 있다. tempMin은 -68 로 업데이트 된다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기