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

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

프로그래머스

코딩테스트 연습 > 월간 코드 챌린지 시즌1 > 풍선 터트리기

 

난이도: LEVEL3

알고리즘 유형: 그리디? 구현 

풀이 설명

규칙 

풍선은 인접한 두 풍선중에 더 작은 풍선을 터트리는 행위는 최대 1번만 가능하다.

최대 1번을 제외하고는 항상 큰 풍선을 터트리는 행위를 한다. 

 

큰 풍선을 터트리면 남는 풍선은 숫자가 더 작은 풍선이다. 

 

내 아이디어

어떤 특정 index의 숫자가 있을 때 해당 숫자가 최후까지 남기는 것이 가능하려면 

양 옆의 구간 숫자들 최소가 왼쪽이든 오른쪽이든 1개는 더 커야 한다. 

 

ex)

...... 숫자들 min = -6     현재 index  숫자 -1    ...... 숫자들 min = -7 

양옆의 구간 숫자들의 min이 둘 다 현재 숫자보다 작으면 작은 풍선을 터트리는 행위가 2번이 필요하다.

그래서 불가능하다.

 

나머지 케이스 작은 경우가 1개 큰 경우가 1개 둘 다 큰 경우는 가능하다. 

 

이 아이디어를 바탕으로 코드를 구현했다. 

 

우선순위 큐 

PriorityQueue<int [] > pq = 
            new PriorityQueue<>((o1, o2) -> {return o1[0] - o2[0];});

인덱스 0: 숫자 인덱스 1: 본래의 인덱스 의미

숫자가 적은 순서대로 나온다.

 

int rightMin = Integer.MAX_VALUE;

현재 숫자보다 오른쪽 구간에 있는 숫자중에 최솟값을 의미 

 

핵심 알고리즘 

for(int i = size - 1; i >= 0; i--){
    while(!pq.isEmpty() && pq.peek()[1] >= i){
        int[] cur = pq.poll();
        if(cur[1] != i) right_min = Math.min(right_min, cur[0]);
    }
    if(!pq.isEmpty() && a[i] < pq.peek()[0] || a[i] < right_min){ 
        answer++;
    }
    else if(i == 0) answer++;
    right_min = Math.min(a[i], right_min);  
}

현재 인덱스를 검사하기 전에 먼저 pq에서 앞의 index 값들을 빼준다.  

 

 i == 0 일 때 pq에 값이 없고 min 값도 마지막 a[0] 보다 크면 answer 추가를 안 한다.

그러나 양 끝의 index는 항상 가능하다. 

정답 코드

import java.util.*;
class Solution {
    public int solution(int[] a) {
        int answer = 0;
        int size   = a.length;

        if(size <= 2) return size;
        
        PriorityQueue<int [] > pq = 
            new PriorityQueue<>((o1, o2) -> {return o1[0] - o2[0];});
        
        int rightMin = Integer.MAX_VALUE;
        for(int i = 0; i < size; i++){
            pq.add(new int [] {a[i], i});
        }
        
        int right_min = Integer.MAX_VALUE;
        for(int i = size - 1; i >= 0; i--){
            while(!pq.isEmpty() && pq.peek()[1] >= i){
                int[] cur = pq.poll();
                if(cur[1] != i) right_min = Math.min(right_min, cur[0]);
            }
            if(!pq.isEmpty() && a[i] < pq.peek()[0] || a[i] < right_min){ 
                answer++;
            }
            else if(i == 0) answer++;
            right_min = Math.min(a[i], right_min);  
        }
        return answer;
    }
}