풍선 터트리기

문제정의

---

나란히 있는 두 풍선을 임의로 선택하여 그 중에 큰 쪽을 터트린다. 단, 한번은 더 작은 숫자의 풍선을 터트릴 수 있다. 풍선이 1개가 남을 때 까지 터트릴 때, 최후에 남을 수 있는 풍선의 갯수를 반환하라.

문제풀이

---

전체 코드는 다음과 같다.

import java.util.ArrayList;

public class BallonPop {

    //프로그래머스 문제풀이 level3 풍선 터트리기

    public static void main(String[] args) {
        int[] a = {9,1,5};
        int[] left = new int[a.length];
        int[] right = new int[a.length];
        
        left[0] = a[0];
        right[a.length-1] = a[a.length-1];

        for(int i = 1; i < a.length; i++)
            left[i] = left[i-1] > a[i] ? a[i] : left[i-1];

        for(int i = a.length-2; i >= 0; i--)
            right[i] = right[i+1] > a[i] ? a[i] : right[i+1];
        
        int answer = 0;
        for(int i = 0; i < a.length; i++)
            answer = (left[i] < a[i]) && (right[i] < a[i]) ? answer : answer+1;
        
        System.out.println(answer);
    }
    
}

한 풍선을 선택하고 그 풍선이 최후로 남을 수 있는 경우의 수를 생각해보면 자신을 기준으로 좌우에서 풍선의 최소값을 각각 구한다. 만약 좌우의 풍선값보다 기준 풍선값의 값이 작다면, 이 풍선은 절대 터트릴 수 없다. 이를 코드로 구현한 것이 위와 같다.

시간 복잡도는 \(O(n)\)이다.

테스트

요새 문제풀이를 통 못했는데 일단 난이도가 어려워져서 고민하는 시간이 많아 포스팅 하는 텀이 길어진다. 물론 이 풀이도 질문하기에서 본 접근방법을 참고한 거라 공부가 많이 필요하다고 느낀다. 패스트캠퍼스에서 주관하는 네카라쿠배 교육과정의 2차테스트를 치르고 있는 중인데, 혼자 공부하는 것보단 학원이 나을 것 같아서 최선을 다해 테스트에 임하려고 한다. 그래도 혼자 공부하는 시간을 줄이진 말아야지. 화이팅!