Programmers - [풍선터트리기]

1. 문제

문제 설명

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

---

제한 사항

• a의 길이는 1 이상 1,000,000 이하입니다.
  • a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
  • a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
  • a의 모든 수는 서로 다릅니다.

---

입출력 예

aresult

[9,-1,-5]	3
[-16,27,65,-2,58,-92,-71,-68,-61,-33]	6

---

입출력 예 설명

입출력 예 #1

• 첫 번째 풍선(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 해야 합니다.

입출력 예 #2

• 최후까지 남을 수 있는 풍선은 -16, -92, -71, -68, -61, -33이 써진 풍선으로 모두 6개입니다.

2. 내풀이

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public int solution(int[] a) {
        int count = a.length;

        for (int i = 0; i < a.length; i++) {
            int bulloon = a[i];
            ArrayList<Integer> leftList = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                leftList.add(a[j]);
            }
            ArrayList<Integer> rightList = new ArrayList<>();
            for (int j = i + 1; j < a.length; j++) {
                rightList.add(a[j]);
            }

            ArrayList<Integer> minlist = new ArrayList<>();

            if (leftList.size() == 0 || rightList.size() == 0) continue;
            minlist.add(minBulloon(leftList));
            minlist.add(minBulloon(rightList));
            minlist.add(bulloon);

            ArrayList<Integer> answerList = new ArrayList<>();
            if (bulloon == maxBulloons(minlist)) {
                answerList.add(bulloon);
                System.out.print(bulloon+ " ");
                count--;
            }


        }
        return count;
    }

    //ArrayList의 최소값의 인덱스를 반환하는 함수
    public int minBulloon(ArrayList<Integer> list) {
        int num = list.get(0);
        for (int i = 0; i < list.size(); i++) {
            if (num > list.get(i)) num = list.get(i);
        }
        return num;
    }

    public int maxBulloons(ArrayList<Integer> list) {
        int num = list.get(0);
        for (int i = 0; i < list.size(); i++) {
            if (num < list.get(i)) num = list.get(i);
        }
        return num;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a = {-16, 27, 65, -2, 58, -92, -71, -68, -61, -33};
        System.out.println(solution.solution(a));
    }
}

- 풍선들을 하나씩 선택해서 해당 풍선은 마지막까지 남겨지는지 확인해서 거른다.

- 선택된 풍선을 제외하고 좌 우 리스트를 만든다음, 왼쪽 리스트에서 가장 작은 풍선를 거르고, 오른쪽 리스트에서 가장작은 풍선를 고른후 세 숫자중 가장 큰숫자가 만약 선택된 풍선이라면 해당 풍선은 마지막 하나까지 남겨지지 못한다.

 

좌, 우에서 가장 작은 숫자만 남기는 것은 어짜피 번호가 더큰 풍선을 터트리는 것은 무한정 할수 있으므로

남겨지는것은 가장작은 숫자만 남겨지기 때문이다.

 

세숫자가 남겨진 상황에서 [-16, -2, -92] 가 남았다고 생각하면

-2와 -16에서 번호가 더 작은 풍선을 터트립니다.

-2와 -92중 번호가 더 작은 풍선을 터트려야 하는데 이미 더 작은 풍선을 터트리는 방법은 사용했으므로

-2는 남겨지지 못합니다. 

 

 

하지만 이방법은 시간초과로 실패했다.

a의 길이가 백만인데 2중 for문을 사용한데다가 좌우 함수를 만들때 ArrayList 자료구조에 add함수를 썻기 때문에 N이 소요되어 총 N의 3제곱 즉 10의 18승 의 계산이 적용되어 시간초과가 된다.

ArrayList 외 배열이나

3. 다른 사람 풀이

package Programmers;

class BrokenBulloons {
    public int solution(int[] a) {
        int count = 0;

        // 가장 작은 값 초기화
        int minValue = Integer.MAX_VALUE;
        // 선택된 풍선이 i 번째 일때 해당 풍선의 왼쪽의 그룹의 에서의 최솟값은 leftMin[i]
        int[] leftMin = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            if (minValue > a[i]) minValue = a[i];
            leftMin[i] = minValue;
        }

        // 선택된 풍선이 i 번째 일때 해당 풍선의 오른쪽의 그룹의 에서의 최솟값은 rightMin[i]
        minValue = Integer.MAX_VALUE;
        int[] rightMin = new int[a.length];
        for (int j = a.length - 1; j >= 0 ; j--) {
            if (minValue > a[j]) minValue = a[j];
            rightMin[j] = minValue;
        }

        for (int i = 0; i < a.length; i++) {
            // 왼쪽과 오른쪽 그룹의 최솟값 보다 크다면 넘어간다. // 최후 까지 남겨지지 못함
            if(a[i] > rightMin[i] && a[i] > leftMin[i]) continue;
            // 나머지는 추가
            else count++;
        }
        return count;
    }

    public static void main(String[] args) {
        BrokenBulloons solution = new BrokenBulloons();
        int[] a = {-16, 27, 65, -2, 58, -92, -71, -68, -61, -33};
        System.out.println(solution.solution(a));
    }
}

- 전체적인 풀이 방식은 같으나 시간초과를 피하려 i 번째 풍선이 선택되었을때 왼쪽그룹의 최솟값은

leftMin[i]에 저장하고 오른쪽 도 마찬가지로 한다.

- i번째 풍선이 왼쪽과 오른쪽 최솟값보다 크다면 남겨지지 못하는 숫자이므로

4. Tip

- 시간 복잡도를 계산해야한다.

- i번째 풍선을 선택하였을 때 필요한 값은 왼쪽 그룹의 최솟값, 오른쪽 그룹의 최솟값인 것을 알아야한다.