JAVA 프로그래머스 Lv.3 풍선 터트리기

 

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

---

문제

1. 입력으로 int 배열 a( 1 <= a.length <= 1000000)이 입력으로 들어옴.
2. a[i]는 i + 1번 풍선에 써진 숫자를 의미함.
3. a[i] (i = 0 ~ a.length)는 ( -1000000000 <= a[i] <= 1000000000)
4. 임의의 인접한 두 풍선을 고른 뒤에 두 풍선 중 하나를 터트린 후 빈 공간이 생기면 빈 공간이 없도록 터진 풍선의 양 옆을 붙여 밀착시킨다.
5. 인접한 두 풍선 중 한 풍선을 터트릴 때 둘 중 더 작은 번호의 풍선을 터트리는 것은 최대 1번만 할 수 있고, 이외에는 모두 큰 번호가 적힌 풍선을 터트려야 된다.
6. 규칙대로 풍선을 1개 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선의 개수를 return.

---

 

초기 코드

import java.util.ArrayList;

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        
        int minA = 1000000000;

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

        for (int n : a) {
            minA = Math.min(n, minA);
            num.add(n);
        }

        for (int n : a) {
            ArrayList<Integer> temp = new ArrayList<>(num);
            int f = 0;
            int t = 1;
            boolean flag = true;
            if (n == minA) {
                answer++;
                flag = false;
            }
            while (flag) {
                if (temp.size() == 2) {
                    if ((temp.get(0) == n && temp.get(1) == minA)
                            || (temp.get(0) == minA && temp.get(1) == n)) {
                        answer++;
                        flag = false;
                        break;
                    } else {
                        flag = false;
                        break;
                    }
                }if (f >= temp.size() || t >= temp.size()) {
                    flag = false;
                    break;
                }
                if ((temp.get(f) == n || temp.get(t) == n)
                        && n == Math.max(temp.get(f), temp.get(t))) {
                    f++;
                    t++;
                } else {
                    temp.remove(temp.indexOf(Math.max(temp.get(f), temp.get(t))));
                }
            }
        }
        
        return answer;
    }
}

 

방식은 맞는 것 같은데 시간 초과가 많이 났다.

테스트 15개 중 3개는 통과하고 나머지가 시간 초과가 난 걸 보니까 중간에 뛰어 넘어야 되는 부분을 내가 전부 실행한 것 같다.

아마도 원하는 수와 min 수를 기준으로 반대편(지나온 곳)에 남은 풍선이 있으면 해당 풍선은  최후에 남을 수 없는 풍선인 것 같다.

 

수정한 코드

import java.util.ArrayList;

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        
        int minA = 1000000000;

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

        for (int n : a) {
            minA = Math.min(n, minA);
            num.add(n);
        }

        for (int n : a) {
            ArrayList<Integer> temp = new ArrayList<>(num);
            int f = 0;
            int t = 1;
            boolean flag = true;
            if (n == minA) {
                answer++;
                flag = false;
            }
            while (flag) {
                if (temp.size() == 2) {
                    if ((temp.get(0) == n && temp.get(1) == minA)
                            || (temp.get(0) == minA && temp.get(1) == n)) {
                        answer++;
                        flag = false;
                        break;
                    } else {
                        flag = false;
                        break;
                    }
                }if (f >= temp.size() || t >= temp.size()) {
                    flag = false;
                    break;
                }
                if ((temp.get(f) == n || temp.get(t) == n)
                        && n == Math.max(temp.get(f), temp.get(t))) {
                    f++;
                    t++;
                    if (temp.get(0) != n && temp.get(0) != minA) {
                        flag = false;
                        break;
                    }
                } else {
                    temp.remove(temp.indexOf(Math.max(temp.get(f), temp.get(t))));
                }
            }
        }
        
        return answer;
    }
}

 

f와 t를 증가시킬 때 증가시킨 이후 temp 배열의 첫 원소가 n이나 minA가 아니면 해당 수를 삭제할 수가 없기 때문에 반복을 멈출 수 있도록 해봤는데 시간 초과는 여전히 발생했기 때문에 다른 방법을 사용해야 될 것 같다.

 

 

새롭게 생각한 방법은 이렇다.

선택한 풍선 n을 기준으로 좌와 우로 나누어 각각의 min을 구한 후 비교하는 방법이다.

두 개의 min 중 하나라도 n보다 크다면 그  n 풍선은 마지막까지 남을 수 있는 풍선이다.

 

이 때 양끝의 수는 배열 전체의 min을 이용할 수 있고 좌 우로 나뉠 필요가 없기 때문에 무조건 마지막까지 남을 수 있게 된다.

 

따라서 전체 배열의 길이가 2보다 크다면 양끝의 수는 모두 마지막까지 남을 수 있으므로 정답을 2부터 시작한다.

 

수정한 코드

class Solution {
    public int solution(int[] a) {
        int answer = 2;
        
        if (a.length > 2) {
            for (int i = 1; i < a.length - 1; i++) {
                int minL = 1000000000;
                int minR = 1000000000;

                for (int j = 0; j < i; j++) {
                    minL = Math.min(minL, a[j]);
                }

                for (int j = i + 1; j < a.length; j++) {
                    minR = Math.min(minR, a[j]);
                }

                if (minL > a[i] || minR > a[i]) {
                    answer++;
                }
            }
        } else {
            answer = a.length;
        }
        
        return answer;
    }
}

 

하나 더 맞긴 했는데 엄청 오래 걸렸고

나머지는 시간 초과가 떴다.

더 수정해야 될 것 같다 시간 복잡도 O(n)정도가 되어야 되는 것 같은데 어떻게 해야 될지 잘 모르겠다.

좀 더 생각해봐야 될 것 같다.

 

수정한 코드

class Solution {
    public int solution(int[] a) {
        int answer = 2;
        
        int minL = a[0];

        if (a.length > 2) {
            for (int i = 1; i < a.length - 1; i++) {
                int minR = 1000000000;

                for (int j = i + 1; j < a.length; j++) {
                    minR = Math.min(minR, a[j]);
                }

                if (minL > a[i] || minR > a[i]) {
                    answer++;
                }

                minL = Math.min(minL, a[i]);
            }
        } else {
            answer = a.length;
        }
        
        return answer;
    }
}

 

시간이 조금 줄긴 했는데 나머지 테스트 케이스들이 여전히 시간 초과가 난다 줄일 방법이 더 필요한 것 같다.

 

 

최종 코드

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        
        int minL = a[0];

        int[] minR = new int[a.length];
        minR[a.length - 1] = a[a.length - 1];

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

        if (a.length > 2) {
            for (int i = 0; i < a.length; i++) {
                if (!(minL < a[i] && minR[i] < a[i])){
                    answer++;
                    minL = Math.min(minL, a[i]);
                }
            }
        } else {
            answer = a.length;
        }
        
        return answer;
    }
}

 

오른쪽 min 변수를 어떻게 해야 될지 모르겠어서 다른 블로그를 조금 참조했다.

 

반복문 안에 들어가는 조건문도 바꾸기 이전에는 엄청 길게 썼었는데 다른 분들은 엄청 짧길래 뭐가 문젠가 했는데 내가 필요한 모든 경우를 적어놓아서 긴 거였고 해당 조건들의 여집합을 구해 해당 조건문을 반전시키면 되는 거였다.

말을 제대로 적었는진 모르겠지만 이대로 하니 짧아져서 보기가 좋았다.

 

오른쪽 min 변수를 int 변수로 사용하려고 했는데 그러면 반복문 안에 반복문이 들어가 중첩되는 형식이 되어서 시간 초과가 계속 났는데.

누적합처럼 다른 칸의 수와 해당 수를 비교하여 오른쪽 min 배열을 만들어 계산하니 시간 복잡도가 낮아져 시간 초과가 뜨지 않았다. 사람들 너무 똑똑한 것 같다.