프로그래머스 - 풍선 터트리기 (C++)

 

 

여러 개의 풍선이 주어지며, 각 풍선에는 숫자가 기입되어 있다.

이 때, 규칙에 맞게 차례대로 풍선을 터트릴 것이다.

모든 경우의 수를 다 따져보았을 때, 최종적으로 남는 1개의 풍선이 될 수 있는 풍선은 몇가지인가를 구하는 문제이다.

 

규칙은 이러하다.

인접해있는 두개의 풍선중 하나를 선택하여 터트린다.

기본적으로는 숫자가 더 큰 풍선을 터트려야 하지만, 딱 1번 숫자가 더 작은 풍선을 터트릴 기회가 있다.

 

그렇다면, 이 문제를 어떻게 풀어야 할까?

 

 

문제 풀이

---

 

처음엔 문제를 읽고 좀 당황했지만, 생각보다 풀이 자체는 간단했다.

 

하나의 풍선을 골랐을 때, 그 풍선의 값보다 더 작은 값을 가진 풍선이 왼쪽에도 있고 오른쪽에도 있다면 그 풍선은 마지막까지 살아남을 수 없다.

 

무슨 말인지 이해다 잘 안될 것이다.

 

경우의 수를 총 4개로 나누어보자.

 

1. 왼쪽과 오른쪽에 모두 현재 풍선의 값보다 작은 풍선이 없는 경우

즉, 현재 풍선의 값이 전체 풍선에서 최소값인 것이다.

그렇다면, 현재 풍선을 기준으로 다른 풍선을 모두 제거할 수 있으므로 마지막에 남는 풍선이 될 수 있다.

 

2. 왼쪽에만 현재 풍선의 값보다 작은 풍선이 1개라도 있는 경우

오른쪽에 있는 풍선은 모두 현재 풍선보다 큰 값을 지니므로 모두 파괴할 수 있다. 왼쪽에 남은 풍선들끼리 서로 파괴하고 나면 마지막에 남는 풍선은 왼쪽 풍선중 최소값을 지닌 풍선일 것이다.

 

왼쪽에서 발견된 현재 풍선보다 값이 작은 풍선을 A라고 해보자. 이 A는 왼쪽 풍선중에서 최소값일 수도 있고, 최소값보다 큰 값일 수도 있다. 하지만 확실한 것은 A는 현재 풍선의 값보다 작다는 것이다.

 

(왼쪽의 최소값 풍선 <= A의 값 < 현재 풍선의 값) 이므로, 왼쪽 풍선끼리 모두 터트리고 마지막에 남은 풍선은 무조건 현재 풍선보다 값이 작다.

 

이 때, 작은 풍선을 터트릴 수 있는 기회를 사용한다면 현재 풍선은 살아남을 수 있다. 

 

3. 오른쪽에만 현재 풍선의 값보다 작은 풍선이 1개라도 있는 경우

위의 경우와 동일하다. 이 경우에도 현재 선택된 풍선이 마지막까지 살아남을 수 있다.

 

4. 왼쪽과 오른쪽에 모두 현재 풍선의 값보다 작은 풍선이 있는 경우

이 경우에 생각을 해보자. 왼쪽 풍선을 모두 터트리고, 오른쪽 풍선을 모두 터트리면 양 옆에 나보다 작은 풍선이 하나씩 생긴다. 둘 중 터트릴 수 있는 풍선은 단1개이므로 마지막엔 선택된 풍선을 터트려야 한다.

고로, 마지막에 살아남을 수 있는 가능성이 없다.

 

즉, 하나의 풍선을 선택했을 때 해당 풍선의 값보다 작은 풍선이 양 옆에 있는 경우가 아니라면 해당 풍선은 마지막까지 살아남을 수 있는 것이다.

 

 

풀이 코드

---

  std::vector<int> Answer;
  Answer.reserve(a.size());
  
  std::vector<std::pair<int, int>> Mins(a.size());

 

답을 저장할 자료구조 Answer를 하나 선언하였다.

Mins는 pair로 값을 받도록 하였는데, first는 왼쪽에 있는 풍선중 최소값이며 second는 오른쪽에 있는 풍선중 최소값이다.

 

Mins[0].first = a[0];

for (int i = 1; i < a.size(); i++)
{
    Mins[i].first = std::min(Mins[i - 1].first, a[i - 1]);
}

Mins[a.size() - 1].second = a[a.size() - 1];

for (int i = a.size() - 2; i >= 0; i--)
{
    Mins[i].second = std::min(Mins[i + 1].second, a[i + 1]);
}

 

이렇게 반복문을 돌며 Mins배열을 모두 채워주었다.

(사실 이렇게 최소값까지 기록할 필요는 없고, 나보다 작은 값이 있나 없나만 비교하는 bool값만 넣어도 된다.)

 

for (int i = 0; i < a.size(); i++)
{
    bool LeftMin = Mins[i].first < a[i];
    bool RightMin = Mins[i].second < a[i];

    if (!(LeftMin == true && RightMin == true))
    {
        Answer.push_back(a[i]);
    }
}

return Answer.size();

 

그 이후, 왼쪽의 최소값이 나보다 작은가? 오른쪽의 최소값이 나보다 작은가? 두 개의 bool값을 저장하였다.

두  bool값이 모두 true인 경우가 아니라면, 해당 풍선의 값을 Answer에 넣어주었다.

마지막엔 Answer만 리턴해주면 된다.

 

 

---

 

코드는 정말 간단하다. 하지만, 아이디어를 구상하는 것이 쉽지가 않은 문제인 듯 하다.