문제 설명
일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.
- 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
- 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.
여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.
당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.
일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- a의 길이는 1 이상 1,000,000 이하입니다.
- a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
- a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
- a의 모든 수는 서로 다릅니다.
풀이
문제를 요약하면, 서로 다른 n개의 풍선 중, 인접한 두 풍선을 골라 특정한 룰에 따라 하나씩 제거하여 마지막에 남을 수 있는 풍선의 개수를 구한느 것이다.
특정한 룰은 조금 특이하다.
기본적으로는 두 풍선 중 더 큰 풍선을 제거한다.
하지만, 단 한 번 더 작은 풍선을 제거할 수 있다.
이렇게만 이해하고 문제를 풀면 갈피를 잡기 힘들다.
처음에는 dp나 dfs 등의 방법을 생각해 봤지만, 제한 사항에 나온 a의 길이가 매우 크기 때문에 n^2까지는 불가능하다고 생각했다.
그러다 발견한 규칙이 하나 있다.
우선, 양끝의 풍선은 무슨 일이 있어도 살아남을 수 있다.
예를 들어, [1, -5, -2, -3, -4, -99, 99]라는 풍선이 있다고 가정해 보자.
기본적인 규칙에 의해 1과 -5를 비교하면 1이 제거된다.
하지만, 단 한 번 작은 풍선을 제거할 수 있으므로 -5를 제거할 수 있다.
즉, 1의 오른쪽에 오는 수가 1보다 크면 기본적으로 제거할 수 있으며, 1보다 작아도 한 번의 찬스를 이용하여 제거할 수 있다.
99도 같은 원리로 무조건 살아남을 수 있다.
그렇다면 중간에 낀 풍선들만 판단하면 된다.
이는, 양 끝의 풍선을 처리했던 것과 똑같은 원리를 적용할 수 있다.
단, 양 끝의 풍선과 달리 양쪽에 대해 판단하면 된다.
중간에 있는 풍선이 마지막에 남는 상황으로 가기 전에 무조건 양쪽에 풍선 1개씩만 남은 상황이 생긴다.
그때, 양쪽이 모두 자신보다 작다면 그 풍선은 절대 마지막에 남을 수 없다.
더 작은 풍선을 터트릴 기회는 1번뿐이기 때문이다.
반대로, 양쪽에 있는 풍선 중 단 하나라도 자신보다 크다면 그 풍선은 마지막에 남을 수 있다.
그럼 양쪽에 어떤 풍선이 오는지 생각해봐야 한다.
양쪽에 올 수 있는 풍선은 해당 방향에 있는 풍선 중 가장 작은 풍선일 것이다.
예를 들어, [1, -5, -2, -3, -4, -99, 99]에서 -2는 마지막으로 다음과 같은 상태가 된다.
[-5, -2, -99] 이때, -5, -99 모두 -2보다 작기 때문에 -2는 마지막에 남을 수 없다.
하지만, -5는 마지막으로 [1, -5, -99] 상태가 된다.
-5는 찬스를 통해 -99를 제거할 수 있고, 1은 -5보다 크기 때문에 제거하여 마지막에 남을 수 있다.
즉, 해당 위치까지의 최솟값을 양방향에서 측정하여 관리하면 문제를 풀 수 있다.
{
int currentMin = a[0];
for(int i = 0; i < a.size(); i++)
{
if(currentMin > a[i]) currentMin = a[i];
left[i] = currentMin;
}
}
{
int currentMin = a[a.size()-1];
for(int i = a.size()-1; i >= 0; i--)
{
if(currentMin > a[i]) currentMin = a[i];
right[i] = currentMin;
}
}
전체 코드
#include <string>
#include <vector>
#include <climits>
#include <iostream>
using namespace std;
int solution(vector<int> a) {
int answer = 0;
vector<int> left(a.size(), 0);
vector<int> right(a.size(), 0);
{
int currentMin = a[0];
for(int i = 0; i < a.size(); i++)
{
if(currentMin > a[i]) currentMin = a[i];
left[i] = currentMin;
}
}
{
int currentMin = a[a.size()-1];
for(int i = a.size()-1; i >= 0; i--)
{
if(currentMin > a[i]) currentMin = a[i];
right[i] = currentMin;
}
}
answer = 2;
for(int i = 1; i < a.size()-1; i++)
{
if(a[i] > left[i] && a[i] > right[i]) continue;
answer++;
}
return answer;
}