Programmers - 풍선 터트리기 with JAVA

 

문제

풍선마다 서로 다른 번호를 가지고 있으며 해당 조건에 따라 풍선을 터트리고자 한다.

조건 1. 인접한 풍선 중에 하나를 터트릴 수 있다.

조건 2. 숫자가 큰 풍선을 터트리되 한번은 숫자가 작은 풍선을 터트릴 수 있다.

이러한 경우, 마지막까지 살아남을 수 있는 풍선의 개수를 구하라.

 

 

 

로직

1. 마지막까지 살아남을 수 있는 풍선을 기준으로 왼쪽의 풍선 중 가장 번호를 작은 풍선의 번호를 구한다. = left_min

2. 마지막까지 살아남을 수 있는 풍선을 기준으로 오른쪽의 풍선 중 가장 번호를 작은 풍선의 번호를 구한다. = right_min

-> 만약, 해당 풍선의 번호가 두 변수보다 작다면 해당 풍선 제거 가능

-> 만약 둘 중 하나보다 작다면 풍선 제거 가능

-> 만약 둘 모두보다 크다면 제거 불가능.

 

=> "해당 풍선을 기준으로 왼쪽에 있는 풍선들, 오른쪽에 있는 풍선들을 터트린다고 가정할 때, 모두 큰 풍선만을 터트린다고 가정한다. 이 후 위의 로직을 적용하면 한번의 작은 풍선을 터트리는 기회를 써서 해당 풍선을 살릴 수 있는지 여부를 체크한다고 생각하면 된다."

 

추가적으로, 가장 작은 수를 구할 때, 우선순위 큐를 사용했고 공간에 여분이 있으므로 항상 해당 수를 제거하는 것이 아닌 방문처리한 수들을 기준으로 제거하여 복잡도를 줄였다. 또한 범위를 보면 배열보다는 맵을 활용하는게 유용하여 맵을 사용하였다.

 

코드

import java.util.*;
class Solution {
    public int solution(int[] a) {
        int answer = 2;
        PriorityQueue<Integer> check = new PriorityQueue<>();
        HashMap<Integer, Boolean> visited = new HashMap<>();
        for(int i=1; i<a.length; i++){
            check.add(a[i]);
            visited.put(a[i], false);
        }
        int minLeft = a[0];
        for(int i=1; i<a.length-1; i++){
            int now = a[i];
            visited.put(now, true);
            int minRight = 0;
            // 꺼내는 수가 방문했다면 제거하고 다시 확인
            while(true){
                minRight = check.peek();
                if(!visited.get(minRight)){
                    break;
                }
                if(visited.get(minRight)){
                    check.poll();
                }
            }
            if(now < minLeft && now < minRight){
                answer += 1;
            }
            if(now < minLeft && now > minRight){
                answer += 1;
            }
            if(now > minLeft && now < minRight){
                answer += 1;
            }
            minLeft = Math.min(minLeft, now);
        }
        return answer;
    }
}

 

 

import java.util.*;
class Solution {
    public int solution(int[] a) {
        int answer = 2;
        PriorityQueue<Integer> values = new PriorityQueue<>();
        HashMap<Integer, Boolean> check = new HashMap<>();
        for(int i=1; i<a.length; i++){
            values.add(a[i]);
            check.put(a[i], false);
        }
        int left_min = a[0];
        int right_min = values.peek();
        for(int i=1; i<a.length-1; i++){
            int now = a[i];
            check.put(now, true);
            if(right_min == now){
                while(check.get(right_min) && values.size() > 0){
                    right_min = values.poll();
                }
            }
            if(left_min > now | right_min > now){
                answer += 1;
            }
            left_min = Math.min(left_min, now);
        }
        return answer;
    }
}