[알고리즘] 프로그래머스 - 풍선 터트리기

풍선 터트리기

2020 월간 코드 챌린지 9월에 나왔던 문제로 1시간 동안 시간초과로 못 푼 문제 ㅜㅜ
대회 당일 작은 값을 가진 풍선을 터트릴 수 있는 기회는 1번이라는 조건을 잘 활용하지 못했다.

// 삭제하고자 하는 위치 : index

//재귀 호출 내 로직

if //풍선 하나 남은 경우 그 값을 저장

else 
   /** 
   index - 1과 비교하여 큰 값을 제거하고 재귀 호출 --- 1
   만약 작은 값을 제거 할 수 있다면 작은 값을 제거하여 재귀호출 --- 2

   //위와 로직 같음
   index + 1과 비교하여 비교하여 큰 값을 제거하고 재귀 호출 --- 3
   만약 작은 값을 제거 할 수 있다면 작은 값을 제거하여 재귀호출 --- 4
   */

로직을 보면 최대 4개의 재귀호출을 진행하므로 log(N^4) 인 것 같다. 당시에는 완전 탐색말고 해법을 찾지 못해 완전 탐색내에서 시간을 줄이기 위해 시간을 쏟았다...

 

해답은 지인 분의 코드와 해설로 알게 되었다. 작은 값을 터트릴 수있는 기회는 1번뿐... 이 조건을 지키려면 여러 상황을 탐색하며 모든 경우의 수를 봐야한다고 생각했지만 아니었다.

 

/**
 [-16, 27, 65, -2, 58, -92, -71, -68, -61, -33]
 우리는 -92 풍선을 남기려고 한다.

 인접한 풍선만 제거가 가능하기 때문에 -92 풍선의 왼쪽에 풍선들과 오른쪽에 있는 풍선들끼리 터트리는 과정을 거친다.
 큰 값의 풍선을 터트리는 것은 횟수 제한없이 가능하기 때문에 -92 풍선 기준으로 가장 작은 값의 풍선들의 왼쪽, 오른쪽에 남   게 된다. [-16,-92, -71]

 -16, -92을 비교했을 때, 큰 -16이 사라지고 
 -92, -71을 비교했을 때, 큰 -71이 사라져서 -92 풍선이 남게 됩니다.

 같은 방식으로 -68을 남기려고 한다면 [-92, -68, -61]이 남게 됩니다.
 -92, -68을 비교했을 때, -68이 크기 때문에 -68을 남기려면 작은 -92를 지워야한다. 현재까지 -68 왼쪽, 오른쪽에서 큰 풍선만   지워왔기 때문에 작은 풍선을 지울수 있는 기회가 한번있다. 따라서 -92를 지울수 있다.

 -68, -61을 비교했을 때, 큰 -61이 사라지기 때문에 -68 풍선이 남을 수 있다. 만약 -68 오른쪽이 더 작은 값이 었다면 앞서 작   은 풍선을 지웠기 때문에 또 작은 풍선을 지울 수가 없다. 따라서 -68 풍선은 남을 수 없었을 거다.
*/

 

전체 코드

시간 복잡도는 O(N)

class Solution {
    public int solution(int[] a) {

            int answer = 0;
            //남기고자 하는 인덱스의 오른쪽 최소값을 저장하기 위해 최대값으로 초기화
            int[] rightMinArray = new int[a.length + 1];
            for (int i = 0; i < rightMinArray.length; i++) {
                rightMinArray[i] = Integer.MAX_VALUE;
            }

            //최소값 저장
            for (int i = a.length - 1; i >= 0 ; i--) {
                rightMinArray[i] = Math.min(rightMinArray[i + 1], a[i]);
            }

            int leftMin = a[0];
            for (int i = 1; i < a.length - 1; i++) {

                leftMin = Math.min(leftMin, a[i - 1]);

                if (!(leftMin < a[i] && rightMinArray[i] < a[i])) {
                    answer++;
                }
            }


            return answer + Math.min(2, a.length);
        }
}

 

 

참고

• 해설