Problem 문제풀이
처음 봤을 때 세그먼트 트리인가..? 하다가 의외로 쉽게 풀 수 있는 문제임을 알게 되었다.
문제 설명을 간단히 하자면 N개의 서로 다른 숫자가 적혀있는 풍선이 있다. 인접한 풍선 중 숫자가
큰 풍선을 터트릴건데 최대 한 번 숫자가 작은 풍선을 터트릴 수 있다. 마지막 까지 남길 수 있는
풍선의 개수를 구하면 된다.
간단히 생각해보면 3그룹으로 나눌 수 있다. 내가 남기고 싶은 풍선을 target이라 하자.
[target 이전의 풍선들] [target] [target 이후의 풍선들]
target 빼고 풍선을 터트리게 되면 풍선들은 다음과 같이 알아서 잘 터져나갈 것이다. (말넘심)
[target 이전의 풍선들 중 최솟값] [target] [target 이후의 풍선들 중 최솟값]
감이 잡히는가? target이 왼쪽 구간의 최솟값 혹은 오른쪽 구간의 최솟값 보다 작은 값일 경우
target은 살아남을 수 있다!!!(감동)
여기까지 생각하고 구간의 최솟값을 빠르게 구하기 위해 세그먼트 트리를 짜던 중 굳이?라는 생각이 들었다.
잘 생각해보면 2*N만에 문제를 풀 수 있다.
-
n의 크기를 갖는boolean배열을 준비한다. -
첫 번째와 마지막 배열값은
true로 바꾼다. 이거까지 설명하면TMI겠죠..? -
풍선을 왼쪽에서 오른쪽으로 훑으면서 target 이전의 풍선들 중 최솟값과 target을 비교한다.
- 만약 target이 더 작으면 배열값을
true로 변경한다.
- 만약 target이 더 작으면 배열값을
-
반대 방향으로도 같은 작업을 반복한다.
-
배열의
true의 갯수를return한다.
1.
vector<bool>res(a_size);
2.
res[0]=true;
res[a_size-1]=true;
3.
int minV = a[0];
for(int i=1;i<a_size-1;i++)
{
if(a[i]<minV)
{
res[i]=true;
minV = a[i];
}
}
4.
for(int i=0;i<a_size;i++)
{
if(res[i])
{
answer++;
}
}
return answer;
세그먼트 트리가 쓰기 귀찮았던 것은 절~~대로 아니다. 아마도… 아니다…
더 좋고 쉬운 방법이 있다면 그 길을 선택하는 것이 알고리즘의 기본이니까!
전체 코드를 남기며 마무리한다.
#include <string>
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<int> a) {
int answer = 0;
int a_size = a.size();
vector<bool>res(a_size);
res[0]=true;
int minV = a[0];
for(int i=1;i<a_size-1;i++)
{
if(a[i]<minV)
{
res[i]=true;
minV = a[i];
}
}
res[a_size-1]=true;
minV = a[a_size-1];
for(int i=a_size-1;i>0;i--)
{
if(a[i]<minV)
{
res[i]=true;
minV = a[i];
}
}
for(int i=0;i<a_size;i++)
{
if(res[i])
{
answer++;
}
}
return answer;
}