[프로그래머스] 풍선 터트리기 with Kotlin

문제

일렬로 나열 된 풍선 n개가 주어진다.

풍선엔 각각의 번호가 부여되어 있으며, 다음 과정을 통해 풍선을 하나만 남기려고 한다.

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

이때 번호가 더 큰 풍선을 터트려야 하며, 딱 한번 번호가 작은 풍선을 터트릴 수 있다.

마지막까지 남을 수 있는 풍선의 개수를 반환하여라.

 

풀이방법

(핵심 아이디어는 다른 사람 블로그를 참조했습니다.)

핵심 아이디어

1. 지정한 풍선이 A라고 할 때, A의 양 옆의 풍선들의 최소값이 A보다 크다면  A는 마지막까지 남을 수 있다.
2. 양쪽 중 한쪽만 최소값이 커도 한 번의 기회를 사용하면 마지막까지 남을 수 있다.
3. 다만 양쪽 다 최소값이 A보다 작다면 A는 마지막까지 남을 수 없다.

주의 사항

1. 풍선이 최대 100만개까지 주어질 수 있기 때문에 일방적인 방법으로 양쪽의 최소값을 구한다면 시간초과가 나온다.
2. 왼쪽의 최소값은 for문을 돌면서 leftMin보다 작은 값이 나오면 값을 변경해주는 방법 사용
3. 오른쪽은 우선순위 큐를 사용하여 해결

개인적인 풀이 과정입니다.

코드

import java.util.*
class Solution {
    fun solution(a: IntArray): Int {
        var answer: Int = 0
        var leftMin = 1000000000
        
        val temp = PriorityQueue<Int>(reverseOrder())
        for(i in 0 until a.size){
            // num보다 작은게 양쪽으로 있으면 안됨
            val num = a[i]
            
            //temp에 현재 값 보다 큰 값이 있으면 temp에서 삭제
            while(temp.isNotEmpty()){
                val q = temp.poll()
                if(q < num){
                    temp.add(q)
                    break
                }
            }
            
            if(leftMin > num) answer += 1
            else temp.add(num)
            
            leftMin = Math.min(leftMin, num)
        }
        
        return answer+temp.size
    }
}