[Programmers] 풍선 터트리기 (Java)

1. 문제요약

코딩테스트 연습 - 풍선 터트리기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

일렬로 나열된 n 개의 풍선이 있다. 풍선들을 아래 규칙에 따라 단 1개만 남을 때까지 하나씩 터트린다고 할 때 최후까지 남기는 것이 가능한 풍선들의 갯수를 구하시오.

 

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트린다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킨다.
3. 번호가 더 작은 풍선을 터트리는 행위는 한 번만 수행할 수 있다.

 

2. 문제예제

[9,-1,-5] 풍선이 주어질 때 다음과 같다.

 

• 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
• 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

 

3. 팩트추출

Fact 1 : 숫자가 낮은 풍선을 터트리는 행위는 한 번만 할 수 있으므로 모든 조합을 탐색할 필요는 없다. 탐색 방향에 맞춰 조합을 쪼개 규칙성을 찾는다. 일부 조합의 결과를 찾는 알고리즘과 전체 조합의 결과를 찾는 알고리즘이 같다면 DP 이다.

 

일단, 풍선의 갯수를 n 이라고 가정하고 n 이 점차 증가했을 때 규칙성을 찾아본다.

 

1) n 이 1 일 때,

무조건 풍선이 남아 있으므로 1 반환

 

2) n 이 2 일 때,

1번 풍선이 작고 2 번 풍선이 큰 경우와 1번 풍선이 크고 2번 풍선이 작은 경우로 나눌 수 있다.

낮은 풍선을 터트리는 찬스 없이도 큰 걸 제거할 수 있으므로 2 반환

 

3) n 이 3 일 때, 가운데 풍선을 기준으로 4 가지 경우의 수로 나눌 수 있다.

 

3-1) 왼쪽이 작고 오른쪽이 큰 경우

1

2

3

1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존

2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존

2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존

 

3-2) 왼쪽이 크고 오른쪽이 작은 경우

3

2

1

1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존

2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존

2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존

= 3-1 경우의 수와 같다.

 

3-3) 왼쪽도 작고 오른쪽도 작은 경우

1

3

2

1번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 2 생존

3번을 제거하고 2번을 제거하면 (큰 것 => 큰 것 순) 1 생존

3번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 2 생존

2번을 제거하고 3번을 제거하면 (작은 것 => 큰 것 순) 1 생존

= 모든 경우의 수를 살펴봐도 중간값은 생존이 되지 않는다.

 

3-4) 왼쪽도 크고 오른쪽도 큰 경우

2

1

3

2번을 제거하고 3번을 제거하면 (큰 것 => 큰 것 순) 1 생존

2번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 3 생존

3번을 제거하고 1번을 제거하면 (큰 것 => 작은 것 순) 2 생존

 

현재 값보다 양 옆에 있는 숫자가 모두 작은 경우에만 생존하지 못 한다.

 

Fact 2 : 이전 결과 값이 그 다음에 영향을 미치지 않고 작은 문제들의 정답이 전체 문제의 정답이 되는 규칙성은 발견되지 않았다. (거의 모든 경우의 숫자가 살아 남으므로) 따라서 DP 나 분할 정복 문제는 아니다. 그러나 생존하지 못 하는 경우의 수로 보면 두 구역 모두 현재 숫자보다 작을 때 한 가지 경우의 수 밖에 없다. 따라서 경우의 수가 적은 여집합을 구한다.

 

Fact 3 : n 이 4일 때, 5일 때도 같은 규칙성이 존재하는지 확인한다. 작은 풍선을 제거하는 규칙을 사용하지 않고 큰 값만 골라 왼쪽, 오른쪽에서 제거한다면 항상 작은 값들만 배치하게 된다. 그렇게 n 이 3일 때로 만들고 위 규칙을 적용하면 결과값이 동일하다. 구역을 확장해도 해당 규칙에는 문제가 없다.

 

4. 문제전략

부분 문제로 보이지 않고 규칙성이 보이지 않으므로 완전 조합 문제로 풀어야 한다. 하지만 생존을 못 하는 여집합 경우의 수는 한 가지이므로 이 점을 고려하여 두 구역의 최솟 값보다 큰 경우의 숫자만 찾아 제외시켜 문제를 풀면 된다.

 

5. 소스코드

class Solution {
    public int solution(int[] a) {
        int count = 0;
        if (a.length == 1) return 1;
        if (a.length == 2) return 2;

        int leftMin = a[0];
        int rightMin[] = new int[a.length];
        rightMin[a.length-1] = a[a.length-1];

        for (int i = a.length - 2; i > 0; i--)
            rightMin[i] = Math.min(rightMin[i + 1], a[i]);

        for (int i = 0; i < a.length; i++) {
            if (!(leftMin < a[i] && rightMin[i] < a[i]))
                count++;
            leftMin = Math.min(leftMin, a[i]);
        }
        return count;
    }
}