[프로그래머스] Level3 - 풍선 터트리기 - ShinJongPark | Sean P

> 문제

문제 : [풍선 터트리기]

> 문제풀이

접근방법이 중요한 문제인 것 같다.

첫번째 접근은 BruteForce로 i번째 자리는 작은수를 터치고, 나머지 큰수를 터쳐서 남는 숫자를 추가해가는 아이디어… 당연히 최소 O(n^2).. Pass..

두번째 접근은 혹시나 풍선의 위치에 상관없이 dp문제일까 싶었지만 아니었다.. Pass..

세번째 접근, 결론은 풍선이 마지막에 하나만 남는 경우를 생각했을 때, 양 사이드 풍선은 어떤 경우에라도 남아있을 수 있다. 이유 ? 왼쪽을 기준으로 최대치 100만개 풍선이 있다고 했을 때, 맨 왼쪽 값을 제외하고 나머지 99만9999개 중 가장 작은 값이 남을 것이다.

맨 마지막에 남은 두 수를 비교하면 크던 작던, 작은 풍선을 1회 터트릴 수 있기 때문에 맨 왼쪽 값이 무조건 남는다.

오른쪽도 마찬가지다.

이 원리를 생각하여 가장자리를 시작으로 큰 수를 없애가며 가장자리 값을 추려가는 방식이다.

import java.util.*;
class Solution {
    public int solution(int[] a) {
        Set<Integer> res = new HashSet<>();
        int extra = a[0];
        res.add(extra);
        for(int i=1; i<a.length; i++){
        	if(extra > a[i]) {
        		extra = a[i];
        		res.add(extra);
        	}
        }
        extra = a[a.length-1];
        res.add(extra);
        for(int i=a.length-2; i>=0; i--) {
        	if(extra > a[i]) {
        		extra = a[i];
        		res.add(extra);
        	}
        }
        return res.size();
    }
    
}

문제 출처 : Programmers

PREVIOUS[프로그래머스] Level3 - 추석 트래픽

NEXT[프로그래머스] Level4 - 징검다리