프로그래머스 Level 3 풍선터트리기

풍선터트리기 (프로그래머스 Level 3)

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

dfs와 bool을 통한 방문 여부를 실제로 체크하는 방식을 생각하였으나
매우 복잡하며, 시간 초과가 발생하였다
(a 요소의 개수가 무척 크다는 점에서 사실 완전탐색으로는 무리라고 느끼기는 하였다)

이후 결국 구현에 고민하다,
직접 풀지 못하고 검색을 하였다

풀이 방식은 굳이 따지자면 ‘그리디’ 알고리즘에 가깝긴 하다
(특정 시점에서 미리 최솟값을 계산해둔다는 점)

구현의 핵심은 특정 풍선의 ‘왼쪽’ 과 ‘오른쪽’에서
i보다 ‘큰 값’이 있어야 한다
1번은 작아도 통과할 수 있기에
두 값 중 하나보다도 작은 값이라면 그 풍선은
‘끝’까지 남을 수 있다
(실제로 구현을 하기 보다는 원리에 주목)

1. leftMin, rightMin으로 각 요소의 ‘인덱스’ 기준으로
   왼쪽과 오른쪽에서 작은 값을 구한다
   이때, 가장 왼쪽과 오른쪽은 구조상 반드시 남을 수 있기에 처음에 포함시킨다
   
2. 그 외의 요소를 돌면서, 해당 index의
   ‘왼쪽’의 가장 작은값(leftMin[i-1])과
   ‘오른쪽’의 가장 작은값(rightMin[i-1])을
   비교하여 하나라도 작다면 answer를 증가
   

Code

#include <vector>

using namespace std;

int solution(vector<int> a) {
	int n = a.size();

	if (n <= 2)
		return n;

	vector<int> leftMin(n), rightMin(n);

	// 해당 인덱스의 풍선을 기준으로
	// 왼쪽에서 가장 작은 값을 찾는다
	leftMin[0] = a[0];

	for (int i = 1; i < n; i++)
	{
		// 현재 시점과 비교하여 적어놓는다
		leftMin[i] = min(leftMin[i - 1], a[i]);
	}

	// 오른쪽에서 가장 작은값을 찾는다
	rightMin[n - 1] = a[n - 1];

	for (int i = n - 2; i >= 0; i--)
	{
		rightMin[i] = min(rightMin[i + 1], a[i]);
	}

	// 양 끝
	int answer = 2; 

	for (int i = 1; i < n - 1; i++)
	{
		// i를 기준으로 (i 자신의 부분은 빼고)
		// 왼쪽에서 가장 작은 값과
		// 오른쪽에서 가장 작은 값을 비교한다
		// 가장 작은값이 a[i] 이상이라면 answer를 증가시킨다
		if (a[i] <= leftMin[i - 1] ||
			a[i] <= rightMin[i + 1])
		{
			answer++;
		}
	}

	return answer;
}