[ 프로그래머스 [ 월간코드챌린지 ] 풍선 터트리기 ] (C++)

프로그래머스의 풍선 터뜨리기(월간 코드 챌린지) 문제이다.

[ 문제풀이 ]

임의의 인접한 두 풍선을 고른 뒤, 그 중 하나의 풍선을 터뜨리는 작업을 진행했을 때, 가장 마지막까지 살아남을 수 있는 풍선의 수를 구해야 하는 문제이다.

임의의 풍선을 터트릴 때는, 1차적으로는 숫자가 더 큰 풍선을 터트려야 한다.

하지만, 터트리는 작업을 진행하는 과정에서, "숫자가 더 작은 풍선을 터트리는 것"을 딱 1번 진행할 수 있다.

그럼 지금부터, "숫자가 더 작은 풍선을 터트리는 것"을 '찬스' 라고 표현하겠다.

본격적으로 문제에 접근해보자.

#1. 무조건 마지막까지 살아남을 수 있는 풍선

풍선의 위치와 상관없이 마지막까지 무조건 살아남을 수 있는 풍선들이 있다. 어떤 풍선들일까 ??

첫 번째는 "숫자가 가장 작은 풍선" 이다.

왜그럴까 ?? 찬스를 사용하지 않는 이상, 숫자가 더 큰 풍선을 터트려야 한다. 그럼, 숫자가 가장 작은 풍선과 어떤 풍선을 비교했을 때, 찬스를 사용하지 않는다면 어떤 풍선이 살아남게될까?? 당연히 숫자가 가장 작은 풍선이 살아남을 것이다.

왜냐하면 숫자가 더 작기 때문에 터질 일이 없다. 따라서, 숫자가 가장 작은 풍선은 무조건 마지막 까지 살아남을 수가 있다.

두 번째는 "숫자가 두 번째로 가장 작은 풍선" 이다.

이 풍선은 어떻게 살아남을 수 있을까 ?? 일단, "숫자가 가장 작은 풍선"을 제외한다면, 위에서 말한 "가장 작은 풍선이 마지막 까지 살아남을 수 있는 이유"와 동일한 이유로 살아남게 될 것이다. 하지만, 이 경우에는, 찬스를 쓰지 않고 온다면, 최종적으로 "숫자가 가장 작은 풍선" vs "숫자가 두 번째로 작은 풍선" 을 비교해야 하는 경우가 생길 것이다.

그럼, 이 때 찬스를 사용해 버린다면 ?? "숫자가 가장 작은 풍선"을 터트려 버릴 수가 있다.

이런 방법을 이용한다면, "숫자가 두 번째로 작은 풍선" 또한 어느 위치에 있던 상관없이 반드시 살아남을 수 있는 풍선이다.

- 숫자가 가장 작은 풍선 & 숫자가 두 번째로 가장 작은 풍선은 반드시 살아남을 수 있는 풍선들이다.

#2. 기본 원리

그럼 본격적으로 풍선을 터뜨리러 가보자.

먼저, 다음과 같은 위치에 있는 풍선이 마지막 까지 살아남을 수 있는지 판단하기 위해서는 어떤 정보들이 필요한지를 생각해보자.

.

위의 그림에서 빨강색 풍선이 살아남을 수 있는지를 판단해보자.

먼저, 각 풍선에 들어있는 숫자는 모르는 상태이다. 그럼, 빨강색이 살아남기 위한 조건을 생각해보자.

왼쪽 3개의 풍선에서 가장 마지막까지 살아남은 풍선을 'A', 오른쪽 4개의 풍선에서 가장 마지막까지 살아남은 풍선을 'B'라고 표현해 보겠다.

그럼 결과적으로, [ A , 빨강색 풍선 , B ] 의 형태가 최종적으로 남게 된다.

이 때, 찬스를 사용해도 살아남지 못하는 경우는 어떤 경우일까 ?? 바로, A와 B둘다 빨강색 풍선보다 작은 경우이다.

이해하기 쉽게 숫자로 표현해보자면, [ 1 , 3 , 2 ] 와 같은 경우이다. 이 경우에는 빨강색 풍선이 살아남게 하기 위해서 어느 한쪽에 찬스를 사용한다 하더라도, 나머지 다른 한쪽의 숫자도 빨강색 풍선보다 작기 때문에 찬스를 써도 결국 살아남지 못하게 된다. 하지만, 반대로 [ 5 , 3 , 2 ] 가 남았다면 ? 이 경우에는, 3과 2를 비교할 때, 찬스를 사용해버린다면 '2'를 없애버릴 수 있고, 5와 3을 비교할 때는 '5'가 없어지므로 이 경우에는 살아남을 수가 있다.

물론, [ 2, 1 , 3 ] 과 같이, 빨강색 풍선이 A와 B 보다 더 작은 숫자라면 당연히 살아남을 수 있을 것이다.

정리해보면 다음과 표현할 수 있다.

# 빨강색 풍선을 기준으로 왼쪽에서 가장 작은 숫자 = A , 오른쪽에서 가장 작은 숫자 = B 라고 했을 때,

   빨강색 풍선이 살아남을 수 있는 조건

   1. 빨강색 풍선 < A , B

   2. A < 빨강색 풍선 < B

   3. B < 빨강색 풍선 < A

위와 같이 3가지 조건이 있다.

즉, 우리는 주어진 n개의 풍선을 순차적으로 탐색을 하면서, 현재 풍선을 기준으로 왼쪽과 오른쪽에 있는 풍선들 중에서의

최소값만 알 수 있다면 해당 풍선이 살아남을 수 있는지 없는지를 판단할 수 있게 된다.

그럼 최소값을 어떻게 구해야할까 ?? 단순하게 생각해보자. 모든 경우를 다 탐색해 보는 것이다.

그런데 여기서 아주 크나큰 문제가 하나 발생하게 된다.

n의 크기가 100만 이다 보니까, 100만개의 풍선을 탐색할 때 마다, 그 풍선을 기준으로 좌측, 우측의 최소값을 찾는 연산을 진행하게 되면, 결과적으로 시간복잡도가 O(n^2) 이라는 시간이 걸리게 되고, 너무나도 오랜시간이 걸리게 된다는 것이다.

따라서, 이 문제를 해결하기 위해서는 조금은 다른 방법이 필요하다.

#3. 새로운 접근

먼저, #1에서 무조건 살아남을 수 있는 2개의 풍선에 대해서 이야기를 했었다.

그럼, 이 친구들은 무조건 살아남을 수 있으니 이 친구들을 기준으로 생각을 해보자.

예를 들어서, 가장 작은 숫자를 가진 풍선의 위치를 A , 두 번째로 가장 작은 숫자를 가진 풍선의 위치를 B라고 이야기 해보자. 그리고 또 단순하게 생각해서 A < B 라고 생각하자. 이 상태에서 C에 위치한 어떤 풍선이 살아남을 수 있는지 생각을 해보자. 지금 이야기한, A , B , C는 풍선의 숫자가 아닌, 풍선이 위치한 곳이다.(배열의 Index번호와 동일한 역할입니다.)

1. A < C < B 인 경우.

이 경우에는 살아남을 수 있을까 ?? 살아남지 못한다. 왜 ?? C번에 위치한 어떤 풍선은, 일단, 주어진 풍선들 중에서 가장 작은 숫자를 가진 풍선도 아니고, 두 번째로 가장 작은 숫자를 가진 풍선도 아니다. 그럼, 가장 최선의 상황을 생각해보자. 가장 작은 숫자와, 두 번째로 작은 숫자는 A와 B가 이미 차지해 버렸으니, C가 세 번째로 작은 숫자를 가진 풍선이 위치한 곳이라고 생각해보자. 그럼에도, C는 A와 B 사이에 있기 때문에 살아남지 못하게 된다.

2. B < C 인 경우. ( 어차피 A < B 이므로, A < B < C 인 상황과 동일 )

이 경우에는 살아남을 수 있을까 ?? 사실 모른다. C번에 위치한 풍선이 살아남을 수 있는지 모른다.

.

이렇게 되 있는 상황을 이야기하는 것인데, C번 풍선을 기준으로 오른쪽에 어떤 풍선들이 있을지 모르기 때문에 살아남을 수 있는지 알 수가 없다.

그럼 이야기를 조금 바꿔보자. 만약 C번에 위치한 풍선이 "세 번째로 작은 풍선이라면 ?"

즉, A번에 위치한 풍선 = 가장 작은 숫자를 가진 풍선

B번에 위치한 풍선 = 두 번째로 작은 숫자를 가진 풍선

C번에 위치한 풍선 = 세 번째로 작은 숫자를 가진 풍선

이렇게 된다면 우리는 살아남을 수 있는지 알 수 있다.

.

이렇게 번호를 붙여보겠다. 위의 번호는 풍선이 위치한 번호를 나타낸 것이지, 풍선에 적혀있는 숫자를 나타내는 것이 아니다.

우리는 숫자를 모른 채 진행할 것이다.

'C'와 3, 4, 5번에 있는 풍선들을 비교했을 때 반드시 C가 살아남을 것이다. 왜 ?? C가 세 번째로 작은 숫자이기 떄문에, A와 B랑 비교하지 않는 이상, C는 반드시 살아남을 수 있다.

그리고, 1 , A , 2 , B 에서는 'A'가 살아남을 것이다. 왜 ?? 'A'가 당연히 가장 작은 숫자이니까 !

그럼 최종적으로 A vs C의 구도가 형성되는데, 이 때 찬스를 한번 사용한다면 ?? C가 살아남게 된다.

즉 ! 단순히 B < C 인 경우에, C가 살아남을 수 있냐? 라고 묻는다면, 대답을 할 수 없지만, C가 "세 번째로 가장 작은 숫자이다." 라는 조건이 붙게 되면, 우리는 C가 살아남을 수 있다는 것을, 정확한 숫자들을 모르지만 대답을 할 수 있게 된다.

3. C < A 인 경우.

이 경우에는 ?? 위와 똑같이 원리가 적용된다. C가 세 번째로 작은 숫자라는 조건이 없다면, 살아남는지 알 수가 없다. 하지만, C가 세번째로 작은 숫자라는 조건이 생긴다면 반드시 살아남을 수 있다는 것을 알 수 있다.

그럼 여기까지 이야기를 한번 정리해보자.

[ 설정 ]

1. 가장 작은 숫자를 가진 풍선의 위치 = A

2. 두 번째로 작은 숫자를 가진 풍선의 위치 = B

3. 세 번째로 작은 숫자를 가진 풍선의 위치 = C

4. A < B 라고 가정한다.

[ C가 살아남기 위한 조건 ]

1. A < C < B 인 경우에는 반드시 살아남지 못한다.
2. B < C 인 경우에는 반드시 살아남을 수 있다.

3. C < A 인 경우 또한, 반드시 살아남을 수 있다.

우리가 위에 과정에서 뭘 했는지를 한번 알아보자. 뭐 어찌저찌 맞는 말을 한 것 같긴 한데 도대체 저 이야기를 왜 했는지를 한번 생각해보자.

우리는 'C번 Index에 위치한 풍선이 살아남을 수 있는지' 에 대해서 이야기를 했다.

그 결과, A < C < B 에 있을 경우에는 살아남는 것이 불가능하지만, 그게 아닌 경우에는 조건부로 가능하다는 것을 알게 되었다.

그 조건이 바로, "C가 세 번째로 작은 숫자를 가진 풍선" 이라는 조건이다. 또한, 위와 같은 논리라면, 정확하게는 모르겠지만, #2에서 언급했던 O(n^2)이 걸리는 방법은 최소한 사용하지 않아도 될 것 같다 라는 것을 눈치챌 수 있다.

즉 ! 우리는 풍선을 아무렇게나 비교하는 것이 아니라, 가장 작은 숫자들 부터 탐색을 진행한다면, 간단한 Index번호들의 비교만으로도, 심지어 실제 숫자들을 비교하지 않더라도 살아남을 수 있는지 아닌지를 판단할 수 있게 된다.

#4. 풍선 터트리기

우리는 가장 작은 숫자들을 가진 풍선들 부터 탐색을 할 것이다. 그리고, 우리는 Index 번호를 이용해서 풍선의 생존 여부를 판단할 것이다. 생존여부를 판단하는 과정에서, 위의 내용인 #3에서 이야기한, 'C가 살아남기 위한 조건' 이 많이 사용되니, 반드시 기억하고 있으면 좋을 것 같다. 본인은 { 풍선이 가진 숫자 , 풍선이 가진 Index번호 } 를 멤버변수로 가지는 구조체를 하나 선언해 주었다. 멤버변수가 단순히 2개이기 때문에, 구조체가 아닌, pair<> 를 사용해도 무관하다.

그리고 해당 구조체를 풍선이 가진 숫자를 기준으로 오름차순으로 정렬을 시켜 주었다.

말로만 진행하면 헷갈릴 수 있으니, 하나의 예시를 가지고 진행해보자.

.

위와 같이 풍선이 주어졌다고 가정해보자. 이를 풍선의 숫자를 기준으로 오름차순 정렬을 하면 다음과 같아진다.

.

그럼, #1에 의해서 우리는 '-2'와 '0'은 반드시 살아남을 수 있다는 것을 알고 있다. 즉, 탐색이 따로 필요한 친구들이 아니다.

하지만, 탐색을 위한 기준을 정해줄 수 있는 친구들이다.

가장 작은 숫자를 가진 풍선의 Index번호는 '1'이고, 두 번째로 가장 작은 숫자를 가진 풍선의 Index번호는 '3'이 된다.

즉, 우리가 위에서 이야기한 A = 1 이고 , B = 3인 경우이다.

세 번째로 작은 숫자부터 탐색을 해보자.

세 번째로 작은 숫자는 '2'이고, 해당 숫자가 가진 Index번호는 '5'이다.

즉, A = 1 , B = 3 , C = 5인 경우이다.

즉, B < C 의 경우에 해당하는 상황이다. 이 경우에 C는 살아남을 수 있을까 ?? 조건만 있다면 반드시 살아남을 수 있다는 것을 우리는 알고 있다. 조건은 ?? 'C가 세번째로 작은 숫자여야 한다 !' 그런데, C는 실제로 세 번째로 작은 숫자이다.

따라서, 숫자 '2'를 가지고 있는 풍선은 반드시 살아남을 수 있다는 것을 알 수 있다.

여기서 한가지 범위를 재설정하는 과정이 필요하다.

그 다음 우리가 탐색할 값은 아마도 '네 번째로 숫자가 작은 풍선'을 탐색하게 될 것인데, '네 번째로 숫자가 작은 풍선'을 탐색할 때에도, 세 번째로 숫자가 작은 풍선을 탐색할 때와 똑같이 가장 작은 숫자와, 두 번째로 작은 숫자의 위치만 파악하고 비교하면 될까?? 극단적인 다음과 같은 예를 한번 살펴보자.

.

위와 같이 풍선이 존재한다고 가정해보자. 이를 정렬을 시켜보면...

.

다음과 같은 형태로 존재하게 된다.

A = 1 , B = 3이 되는 것이다.

세 번째로 작은 숫자인 '2'를 탐색해보니 C = 5가 되고, B < C 이므로 '2'는 살아남게 된다는 것을 알 수 있다.

그리고, 이 상태에서 네 번째로 작은 숫자인 '3'을 탐색해보자.

C = '4'가 된다. 이 경우에도  A = 1 , B = 3 이므로, B < C가 되기 때문에, 네 번째로 작은 숫자인 '3'은 살아남을 수 있다라고 계산을 해도 될까 ?? 실제로 계산을 해보면 알겠지만, 위의 예시에서 '3'은 무슨 일이 있어도 터져야만 하는, 절대로 살아남지 못하는 풍선이다.

그럼, 여기서 한번 정리를 하고 가자. 도대체 A가 뭐고 B가 뭘까 ?? 지금까지 잘 써왔지만, A와 B가 가지는 의미에 대해서 한번 생각을 해보자.

A와 B가 가지는 의미는 이렇게 정의할 수 있다.

"나보다 더 작은 숫자들이 존재하는 범위" 라고 할 수 있다.

즉 ! 네 번째로 작은 숫자를 탐색할 때에는, "나보다 더 작은 숫자들"에 가장 작은 값과, 두 번째로 작은 값만 포함되는 것이 아닌, 세 번째로 작은 값 또한 포함이 되어지게 된다. 따라서 범위에 대한 재설정이 필요하다.

어떻게 재설정을 해줄까 ?? A = 1 , B = 3 이였지만, C = 5 이고, 이 친구는 살아남았기 때문에, 범위가 A = 1 , B = 5 로 변하게 된다. 이 상태에서, 네 번째로 작은 숫자인 '3'을 다시 탐색해보자. 즉, C = 4 가 되는 것이다.

그럼, A,B,C의 관계식을 적어보면, A < C < B 이기 때문에, 이 경우에는 살아남지 못한다는 것을 우리는 알고 있다.

따라서, 네 번째로 작은 숫자인 '3'은 반드시 터져야만 하는 풍선이 된다.

그럼 다 섯번째로 작은 숫자를 탐색할 때에는 또 A와 B의 값을 재설정 해주어야 할까 ??

그럴 필요가 없다. 왜 ?? 네 번째로 작은 숫자인 '3'은 반드시 터져야만 하는 풍선이기 때문에, 결과에 영향을 줄 수 있는 풍선이 아니기 때문이다. 즉 ! A < C < B 라는 조건이 성립해서, 이 풍선은 절대로 살아남을 수 없다 라는 것을 알게 된다면, 이 경우에는 A와 B의 범위에 대한 재설정이 필요하지 않다.

이야기를 하다가 원래 진행하고 있던 예시에 대해서 설명이 끊겨버렸다.

위와 같은 원리로 우리는 문제를 해결할 수 있다.

마지막으로, 우리가 원래 진행하고 있던 예시에서 살아남을 수 있는 풍선들을 간단하게 정리만 하고 글을 마치겠다.

 [ 초기 A = 1 , B = 3 ]

1. 세 번째로 작은 숫자 '2' : C = 5

   B < C 이므로 반드시 살아남을 수 있다.

   범위의 재설정 : A = 1 , B = 5

   현재까지 살아남은 풍선의 갯수 : 1

2. 네 번째로 작은 숫자 '3' : C = 0

   C < A 이므로 반드시 살아남을 수 있다.

   범위의 재설정 : A = 0 , B = 5

   현재까지 살아남은 풍선의 갯수 : 2

3. 다섯 번째로 작은 숫자 '4' : C = 4

   A < C < B 이므로 반드시 터지는 풍선이다.

   반드시 터지는 풍선이므로, 범위의 설정에 영향을 주지 않는다.

   A = 0 , B = 5

4. 여섯 번째로 작은 숫자 '6' : C = 6

   B < C 이므로 반드시 살아남을 수 있다.

   범위의 재설정 : A = 0 , B = 6

   현재까지 살아남은 풍선의 갯수 : 3

5. 일곱 번째로 작은 숫자 '7' : C = 2

   A < C < B 이므로 반드시 터지는 풍선이다.

탐색종료.

최종적으로 살아남은 풍선의 갯수 = 3개. 하지만 우리가 구한 살아남은 풍선의 갯수만 3개이고, 실질적으로 반드시 살아남을 수 있는 풍선 2개가 더 있으므로, 최종 정답 = 3 + 2 = 5

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
struct BALLON
{
    int Num;
    int Idx;
};
 
int Min(int A, int B) { return A < B ? A : B; }
int Max(int A, int B) { return A > B ? A : B; }
 
bool Cmp(BALLON A, BALLON B)
{
    if (A.Num < B.Num) return true;
    return false;
}
 
int solution(vector<int> a) 
{
    if (a.size() <= 2) return a.size();
    int answer = 0;
    vector<BALLON> Arr(a.size());
 
    for (int i = 0; i < a.size(); i++)
    {
        Arr[i].Num = a[i];
        Arr[i].Idx = i;
    }
    sort(Arr.begin(), Arr.end(), Cmp);
 
    int Idx = Min(Arr[0].Idx, Arr[1].Idx);
    int IIdx = Max(Arr[0].Idx, Arr[1].Idx);
 
    for (int i = 2; i < Arr.size(); i++)
    {
        int Cur_Idx = Arr[i].Idx;
        if (Idx < Cur_Idx && Cur_Idx < IIdx) continue;
        
        answer++;
        Idx = Min(Idx, Cur_Idx);
        IIdx = Max(IIdx, Cur_Idx);
    }
    return answer + 2;
}