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

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

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

 

풍선 두개를 선택하고 두개 중 하나를 터트리는데, 

번호가 더 작은 풍선을 터트리는 것은 단 한번만 할 수 있다.

 

a가 다음과 같을 때 

[-16,27,65,-2,58,-92,-71,-68,-61,-33]

-16 풍선을 남길수 있는지 생각해보자.

번호가 더 작은 풍선을 터트리는 것은 한번만 할 수 있기 때문에 

마지막에 풍선 두개가 남았을때 (-16과 어떤 풍선), 

또 다른 풍선이 -16보다 큰 값일 때를 대비해 마지막까지 남겨 놓아야 한다.

 

그말은 두개의 풍선씩 비교했을때 작은 풍선 만이 남는다는 뜻이고 결국 -16을 제외하고 제일 작은 값의 풍선이 남을것이다.

[-16, -92]

이때 아직까지 번호가 더 작은 풍선을 터트릴수 있는 기회를 사용하지 않았기 때문에 -92를 터트리면 되고,

-16은 최후까지 남을수 있다.

 

위의 말을 정리해보면 하나의 풍선이 최후까지 남을수 있는지 아닌지 판단할때

해당하는 풍선 양쪽에서 두 풍선씩 비교했을때 큰 풍선만이 터질 것이며 

결국 마지막에는 

(해당하는 풍선의 좌측의 최솟값을 갖는 풍선, 해당하는 풍선, 해당하는 풍선의 우측의 최솟값을 갖는 풍선)

이렇게 남을것이다.

이렇게 3개의 풍선이 남았을때 만약 양쪽에 있는 풍선이 둘 다 가운데에 있는 풍선보다 작은 값이라면

이 풍선은 터트릴수 없다는 것을 알 수  있다.

 

즉 이 문제는 모든 풍선들마다 좌측 최솟값과 우측 최솟값을 구하는 문제다.

그런데 배열의 최대 크기가 100만이기 때문에 그냥 일일히 구하는것은 불가능하며

정렬되어 있는 것도 아니기 때문에 이분탐색도 불가능하다.

 

방법은 처음에서 부터 끝까지, 

그리고 끝에서부터 처음까지 두번 순회를 도는 것이다.

 

[-16,27,65,-2,58,-92,-71,-68,-61,-33]

 

위 배열에서 처음부터 끝까지 순회를 돌면서 최솟값을 갱신하면 

-16 -16 -16 -16 -16 -92 -92 -92 -92 -92

 

끝에서부터 처음까지 순회를 돌면서 최솟값을 갱신하면

-92 -92 -92 -92 -92 -92 -71 -68 -61 -33

 

즉 해당 하는 풍선의 좌측 최솟값과 우측 최솟값을 구할수 있다.

 

-16	27	65	-2	58	-92	-71	-68	-61	-33
-16	-16	-16	-16	-16	-92	-92	-92	-92	-92
-92	-92	-92	-92	-92	-92	-71	-68	-61	-33