[programmers][월간 코드 챌린지 시즌1] 풍선 터트리기

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

---

서로 다른 숫자가 써져 있는 n개의 풍선이 있을 때, 인접한 두 풍선을 고른 뒤 두 풍선 중 큰 풍선을 터트린다고 하자. 최후까지 남아있을 수 있는 풍선을 구해라. 이 때, 단 한 번 번호가 더 작은 풍선을 터트릴 수 있다.

---

x 번 풍선이 최후에 남아있을 수 있는지는 x를 기준으로 왼쪽에 있는 풍선들 중 가장 작은 수(1번을 제외하고는 큰 풍선을 터트리므로 작은 수만 남는다.), 오른쪽에 있는 풍선들 중 가장 작은 수를 구한 뒤 왼쪽, 오른쪽 수들 중 1개 이하의 x번 풍선의 수보다 큰 풍선이 있다면 x번 풍선은 최후까지 남아있을 수 있다. 만약 왼쪽에 있는 풍선들 중 가장 작은 수가 10. 오른쪽 풍선들 중 가장 작은 수가 20. x가 15라고 한다면, 15, 20 중 큰 풍선인 20(오른쪽 풍선)을 터트린 후, 10, 15 중 단 한 번의 기회를 써 작은 풍선인 10(왼쪽) 풍선을 터트리면 x번 풍선은 제일 마지막까지 남아있을 수 있다.

 

이를 구하기 위해 왼쪽 부터 탐색하면서 현재까지 탐색한 수 중 가장 작은 수를 저장하는 배열(let, leftMin) 1개, 오른쪽부터 탐색하면서 현재까지 탐색한 수 중 가장 작은 수를 저장하는 배열(let, rightMin) 1개를 세팅한다.

leftMin[x-1], rightMin[x+1] 중 x번 풍선 번호보다 작은 수가 1개 이하이면 x번 풍선이 살아남을 수 있는 경우다.

 

시간복잡도는 O(N)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9C%EC%A6%8C1/%ED%92%8D%EC%84%A0%20%ED%84%B0%ED%8A%B8%EB%A6%AC%EA%B8%B0.cpp