프로그래머스: 풍선 터트리기 [JAVA]

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 배열의 좌측에서 우측으로 진행하며 0부터 현 위치까지의 최소값 계산해 저장
2. 배열의 우측에서 좌측으로 진행하며 배열 마지막부터 현 위치까지의 최소값 계산해 저장
3. 배열 양 끝을 제외한 각 위치(i)에 대해 0~i-1 까지의 최소값, 현 위치 값, i+1~배열 마지막 까지의 최소값 3개를 비교해 값 계산. (이 때 현 위치 값이 남은 2개의 값보다 크지만 않다면 답 +1)

 문제에서 요구하는 과정(인접한 2개를 뽑아 계산)을 반복하기에는 a의 길이가 최대 1,000,000 정도기 때문에 시간 초과가 발생할 수 있다. 이를 피하려면 현 위치의 값을 제외한 다른 부분에 대해서는 일괄적으로 값을 계산해야 하는데, 이 때 문제 요구하는 기본 조건인 인접한 2개의 풍선에 대해 큰 값을 터트리는 것을 적용한다.

 배열의 양 끝을 제외하면 배열의 특정 위치 기준으로 양쪽으로 2개의 구간이 나오고, 문제에서는 딱 한 번만 인접한 2개의 풍선 중 작은 값을 터트릴 수 있기에, 해당 과정을 최대한 뒤로 미뤄두고 단순 큰 값만 터트리는 것을 양쪽 구간에 적용하면, 결과적으로 하나의 구간에서 최소값만이 나오게 된다. 그렇게 되면 결과적으로 3개의 값(왼쪽 구간에서 최소값, 현 위치 값, 오른쪽 구간에서 최소값)만이 나오게 된다. 이후 남은 3개의 값에 대해서는 인접한 2개의 풍선에 대해 작은 값을 터트려도 된다는 조건을 살려, 현 위치의 값이 최종적으로 살아남을 수 있는 지를 계산하면 된다. 이또한 현 위치의 값이 남은 2개의 값보다 크지만 않는다면 무조건 가능하다.

 이 때 특정 위치 기준 왼쪽, 오른쪽 구간의 최소값을 계산하는 것을 최적화하기 위해, 양쪽 구간 값을 dp를 이용해 순차적으로 배열을 채워놓은 다음 활용하면 더욱 빨리 계산을 할 수 있다.

 

class Solution {
    public int solution(int[] a) {
        int answer, arrayLength = a.length;
        int[] leftToRight = new int[arrayLength], rightToLeft = new int[arrayLength];

        if (a.length == 1) {//길이 1개짜리
            return 1;
        }else {
            answer = 2;
        }

        leftToRight[0] = a[0];
        for (int i = 1; i < arrayLength; i++) {//왼쪽 -> 오른쪽으로 가며 최소값 저장
            leftToRight[i] = Math.min(a[i], leftToRight[i - 1]);
        }

        rightToLeft[arrayLength - 1] = a[arrayLength - 1];
        for (int i = arrayLength - 2; i >= 0; i--) {//오른쪽 -> 왼쪽으로 가며 최소값 저장
            rightToLeft[i] = Math.min(a[i], rightToLeft[i + 1]);
        }

        //각 위치(i)에 대해 a[i], 0~i-1까지 중 최소값, i+1~마지막까지 중 최소값에서 비교
        for (int i = 1; i < arrayLength - 1; i++) {
            if (!(a[i] > leftToRight[i - 1] && a[i] > rightToLeft[i + 1])) {//a[i]가 그 중 최대값만 아니라면
                ++answer;
            }
        }

        return answer;
    }
}

결과