프로그래머스 - 택배상자

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

프로그래머스

 

스스로 풀지 못한 문제다.

stack 을 사용하고 하나의 for 문을 쓰면서 트럭에 싣을때마다 target 이라는 int 를 증가시키면서

남은 배열과 stack 에서 우선순위에 맞게 트럭에 싣을 수 있는 택배가 있는지 체크한다.

 

라는 생각은 했는데 처음 우선순위를 확인하기 위한 전처리를 생각하지 못했다.

 

import java.util.*
class Solution {
    fun solution(order: IntArray): Int {
        var answer: Int = 0
        val priority = IntArray(order.size)
        var stack = Stack<Int>()
        var target = 0 // 현재 담을 수 있는 우선순위 index
        for(i in 0 until order.size){
            priority[order[i]-1] = i
            //나머지 코드는 흡사하게 작성했었는데priority[order[i]-1] = i
            //이런식으로 우선순위만을 담는 array를 만들 아이디어를 떠올리지 못했다
        }
        
        for(i in 0 until priority.size){
        	//우선순위가 담긴 array 와 현재 트럭에 싣을 수 있는 우선순위 index 와 비교
            if(priority[i] == target){
            	//담을 수 있는 우선순위라면 트럭에 싣으면서 target 을 증가하여 다음 우선순위 택배를
                //찾는다
                target++
            }else{
            	//담을 수 없다면 보조밸트로 뺸다.
                stack.add(priority[i])
            }
            //target 이 증가했고 스택의 가장위에 있는 택배 우선순위가 증가된 target과 같은지 체크
            while(stack.isNotEmpty() && stack.peek() == target){
            	//보조밸트에서 쓸 수 있는 택배가 있다면 target 을 증가시키고
                //보조밸트에서 pop
                target++
                stack.pop()
            }
        }
        
        return target
    }
}

 

헤매다가 위 코드처럼 우선순위만을 따로 담는 array 를 만들면

내가 풀어보려고 했던 풀이가 퍼즐이 들어맞는다는걸 알게됐다.

 

항상 접근법를 떠올리고 얼추 비슷하게는 짜는데 결정적인 아이디어를

떠올리지 못하는거 같다.. 아직 경험이 부족한듯하다 ㅠㅠ