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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/68646

코딩테스트 연습 - 풍선 터트리기

문제 풀이는 다음과 같다.

1. 벡터의 맨 왼쪽값과 맨 오른쪽 값은 무슨일이 있어도 끝까지 살아남을 수 있다. 때문에 정답값은 2부터 카운팅을 시작하게 된다.

2. 이제 a[i]를 기준으로 왼쪽에서 가장 큰 값을Left, 오른쪽에서 가장 큰 값을 Right라고 지칭해보자
Left와 Right은 맨 처음에는 a[0], a[a.size()-1]로 설정이 될 것이다.
a[i]의 값이 끝까지 생존하려면 Left와 Right값 중 적어도 1개의 숫자가 a[i]보다 커야한다.
Left, Right의 값 중 최소 1개가 a[i]보다 크다면 작은 숫자의 풍선을 터트리는 것을 1번 활용하여 a[i]를 끝까지 남길 수 있기 때문이다.

* a[i]의 생존 조건 : Left > a[i] || Right > a[i]

3. 때문에 왼쪽과 오른쪽에서 for문을 진행하며 위의 2번 조건이 해당되는지 판단한다. 해당될경우 a[i]번째는 살아남을 수 있다고 bool문을 통해 체크해준다.

4. 3번과 동시에 Left > a[i]일 경우, Left의 값은 a[i]로 갱신해준다. 마찬가지로 Right > a[i]일 경우, Right의 값은 a[i]로 갱신해준다. 이렇게 점점 큰 수를 갱신해주면서 변경되는 a[i]의 값에 따라 a[i]가 비교해야하는 가장 큰 Left, Right 값을 비교할 수 있다.

#include <string> 
#include <vector> 
using namespace std; 
int solution(vector<int> a) { 
	int answer = 2, pos ,left = a[0], right = a[a.size()-1]; 
	vector<bool> ch(a.size()); 
	for(int i=1; i<a.size()-1; i++){ 
		pos = a[i]; 
		if(left>a[i]){ 
			ch[i] = true; left = a[i]; 
		} 
	} 
	for(int i=a.size()-1; i>=1; i--){ 
		pos = a[i]; 
		if(right>a[i]){ 
			ch[i] = true; right = a[i]; 
		} 
	} 
	for(int i=1; i<a.size()-1; i++) if(ch[i]) answer++; 
	return answer; 
}