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

 

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/68646

 

n개의 풍선이 일렬로 나열되어 있다고 하자. 이 때, 모든 풍선에는 서로 다른 숫자가 써져 있다.다음 규칙에 따라 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터뜨리려고 한다.

 

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

여기서 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터뜨리는 행위는 최대 1번만 할 수 있도록 제한 되어있다.즉, 한번이라도 인접한 두 풍선 중 번호가 더 작은 풍선을 터뜨리면 이후에는 번호가 큰 풍선만 터뜨려야 한다.

 

이 규칙에 따르면 어떤 풍선은 어떤 방법을 쓰더라도 절대 마지막까지 남길 수 없다.

이때, 최후까지 남기는 것이 가능한 풍선들의 개수를 return하면 되는 문제다.

 

 

제한 사항

 

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

 

 

입출력 예

 

 

a	result
[9,-1,-5]	3
[-16,27,65,-2,58,-92,-71,-68,-61,-33]	6

 

 

풀이

 

이 문제는 쉽게 생각할 수 있는 문제다. 인접한 두 풍선을 골라 터뜨리면 숫자가 큰 풍선을 터뜨려야 하므로, 어떤 풍선을 남기고 싶으면 남기고 싶은 풍선을 기준으로 양 옆을 전부 터뜨리면 된다.

 

아래 그림을 보면 더 이해가 쉬울 것이다.

 

풍선이 위와 같이 나열되어 있을때, b 풍선을 남기고 싶으면 먼저 왼쪽와 오른쪽의 풍선들을 전부 터뜨린다.

 

만약 c>d, d<e의 관계라면 아래와 같이 풍선이 남게 된다.

이후 a와 b를 비교하고 b와 d를 비교하면 된다.

 

이 때, 숫자가 더 작은 풍선을 터뜨릴 수 있는 기회는 한 번 뿐이므로, b는 a와 d 풍선 중에 하나라도 숫자가 작으면 b 풍선을 남길 수 있게 된다.

(a<b<d의 관계면 a, b를 비교할 때 숫자가 더 작은 a 풍선을 터뜨리는 기회를 사용할 수 있기 때문이다.)

 

그러므로 n개의 풍선이 나열된 정보를 바탕으로 i번째 풍선을 기준으로 왼쪽에 있는 풍선 중 가장 작은 숫자, 오른쪽에 있는 풍선 중 가장 작은 숫자를 배열에 저장하고 이를 비교해 answer를 return 하도록 코드를 짰다.

 

[풀이 요약]

1. i번째 풍선을 기준으로 왼쪽에 남아있는 풍선 중 가장 작은 숫자, 오른쪽에 남아있는 풍선 중 가장 작은 숫자를 구한다.
2. 첫번째 풍선부터 n번째 풍선까지 탐색하며 오른쪽 풍선의 가장 작은 숫자와 왼쪽 풍선의 가장 작은 숫자를 비교해 남길 수 있는지 판단한다.
3. 최종 answer를 return한다.

 

Code

 

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> a) {
    int answer = 0;
    int leftMin[1000000];
    int rightMin[1000000];
    fill_n(leftMin,1000000,1000000001);
    fill_n(rightMin,1000000,1000000001);
    int LMV=1000000001;
    int RMV=1000000001;
    for (int i=1; i<a.size(); i++)
    {
       if (a[i-1]<LMV)
       {
           LMV=a[i-1];
       }
        leftMin[i]=LMV;
    }
    for (int i=a.size()-2; i>=0; i--)
    {
       if (a[i+1]<RMV)
       {
           RMV=a[i+1];
       }
       rightMin[i]=RMV;
    }
    for (int i=0; i<a.size(); i++)
    {
        if (a[i]<leftMin[i] ||a[i]<rightMin[i])
        {
            answer+=1;
        }
    }
    return answer;
}

 

 

풀이

 

다른 사람의 풀이를 보던 중 stack을 이용한 풀이가 있길래 stack과 같은 자료구조를 활용해서 풀어봤다.

 

만약 풍선이 {-16, -2, -5, 3} 으로 주어졌다고 가정해보자. 그러면 다음과 같이 stack에 쌓을 수 있다.

 

stack의 가장 위에 있는 숫자보다 현재 풍선의 수가 작다면 stack의 위에 있는 숫자를 빼는 것이다.

 

여기서 비교 후 맨 위 숫자를 뺀다면 stack이 비어있는지를 확인해야 한다.

 

확인 했을 때, 뺀 숫자가 가장 작은 숫자였으므로 answer에서 -1을 할 필요가 없다. (왼쪽에 자신보다 작은 수가 없다는 뜻이므로 오른쪽 풍선중에 가장 작은 수를 터뜨리는 기회를 사용해 그 풍선을 남길 수 있다.)

 

만약 stack이 비어있지 않다면, 그 수는 어떤 수를 사용해도 남길 수 없는 숫자라는 뜻이다.

 

 

[풀이 요약]

1. stack이 비어있는지 보고 비어있다면, 숫자를 쌓는다.
2. 다음 숫자가 stack의 맨 위 숫자보다 큰지 비교하고, 크다면 숫자를 쌓는다.
3. 숫자가 stack의 맨 위 숫자보다 작다면 stack의 맨 위 숫자를 빼고 뺀 다음 stack이 비어있는지 확인해 answer에서 1을 뺄지 결정한다.
4. stack에서 숫자를 뺐다면, 다시 남은 수 중 stack의 맨 위 숫자와 현재 숫자를 비교하고 위 과정을 반복한다.
5. 최종 answer를 return한다. 

 

Code

 

 

#include <vector>
#include <stack>
using namespace std;

int solution(vector<int> a) {
    int answer = a.size();
    stack<int> bStack;
    for (int i=0; i<a.size(); i++)
    {
        if (bStack.empty())
        {
            bStack.push(a[i]);
        }
        else
        {
            while (!bStack.empty()&&bStack.top()>a[i])
            {
                bStack.pop();
                if (!bStack.empty())
                {
                    answer-=1;
                }
            }
            bStack.push(a[i]);
        }
    }
    return answer;
}

 

 

---

 

크기를 비교하는 문제는 stack과 같은 자료 구조를 활용해 푸는 경우가 은근 있는 것 같다

 

 

프로그래머스