[알고리즘] Programmers - 풍선 터트리기

프로그래머스

문제 설명

• 일렬로 나열된 n개의 풍선이 정수형 배열로 a로 주어진다.
• 모든 풍선은 서로 다른 숫자가 써져 있다. 
• 다음과 같은 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트린다.
  1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트린다.
  2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 중앙으로 밀착시킨다.
• 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있다. (어떤 시점에서 작은 것을 터트렸다면 그 뒤로는 큰 것만 터트릴 수 있다.)
• 어떤 풍선이 최후에 남는지 찾아야 한다. 위의 조건대로 풍선을 터트리다 보면, 어떤 풍선은 어떤 경우에서도 마지막까지 남는 것이 불가능할 수도 있다.
• 최후까지 남기는 것이 가능한 풍선들의 개수를 반환해야 한다.

문제 해결

• 양쪽 끝 풍선은 항상 남길 수 있다. 왼쪽 끝 풍선을 예를 들어보겠다.
  1. 배열의 0번 째부터 마지막(length - 1)번까지의 풍선들 중 번호가 더 큰 풍선을 터트린다.
  2. 마지막 남은 두 풍선은 왼쪽 끝 풍선과 나머지(1 ~ length - 1) 풍선 중 최댓값을 가진 풍선이 남는다.
  3. 따라서 한번은 번호가 더 작은 풍선을 터트리는게 가능하기 때문에, 왼쪽 끝 풍선은 번호가 크든 작든 터트리는게 가능하다.
• i 번째 풍선도 비슷한 관점에서 접근하면 된다. i 기준 왼쪽(0 ~ i - 1)범위 또는 i 기준 오른쪽 (i + 1 ~ length - 1)범위의 최댓값이 i 번째 풍선보다 크다면 i 번째 풍선도 남길 수 있다. (양쪽 두 범위의 최댓값 중에서 i 번째 풍선보다 큰 경우가 있다면 가능하다.)
• 위 조건들을 충족하는 풍선들을 찾아서 개수를 세서 반환하면 해결할 수 있다.

시간 복잡도

• O(N)

풀이 코드

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int answer = 2;
        int leftMin = a[0];
        int rightMin = a[a.length - 1];
        
        if (a.length == 1) {
            return 1;
        }
        
        for (int i = 1; i < a.length - 1; i++) {
            // 왼쪽의 최댓값이 현재 값보다 큰 경우 (남기는 것 가능)
            if (leftMin > a[i]) {
                leftMin = a[i];
                answer++;
            }
            // 오른쪽의 최댓값이 현재 값보다 큰 경우 (남기는 것 가능)
            if (rightMin > a[a.length - 1 - i]) {
                rightMin = a[a.length - 1 - i];
                answer++;
            }
            // 배열의 크기가 홀수라 중간에 만나는 경우 answer 1감소 및 반복문 중지
            // 모든 수는 다 다르다고 했으므로 중간에 만나는 것말고 같을 경우는 없음
            if (leftMin == rightMin) {
                answer--;
                break;
            }
        }
        
        return answer;
    }
}

결과

테스트 케이스 통과 (15 / 15)