프로그래머스 LV2 - 다리를 지나는 트럭

요즘 프로그래머스에 있는 알고리즘 고득점 Kit 문제들을 풀고 있다.

사용하는 자료구조별로 정리되어있기 때문에, 어떤 식으로 접근해야 하는지 조금이나마 힌트가 되는게 아쉽지만,

사실 해당 자료구조보다 더 좋은 방법을 발견하기도 하기 때문에 큰상관은 없는듯 하다.

이 문제는 스택/큐 로 분류 되는 문제이다.

 

문제의 카테고리가 "스택/큐"이다보니, 일단은 큐로 시도한다.

큐를 사용하는것 까진 뻔하나,  이 문제의 관건은 "시간" 이다.

시간이 흐르는 것을 어떠한 방식으로 구현할것이냐 의 문제다.

그래서 큐를 허수로 가득 채우고, 하나를 꺼낼때마다 시간 +1 하는것으로 구현하기로 한다.

하나 poll 한 후, 트럭 또는 허수를 다시 채워넣는것이다.

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        
        Queue<Integer> bridge = new LinkedList<>();
        int nextIndex = 0;
        int currentTime = 0;
        int currentWeight = 0;

		//첫 트럭이 다리를 건너 도착하기 까지의 시간을 구현하기 위해 다리길이 만큼 허수를 넣는다.
        for(int i = 0; i< bridge_length; i++){
            bridge.add(0);
        }

        boolean isValidIndex = true; // 다음 트럭이 있는가?
        while(!bridge.isEmpty()){
            currentWeight -= bridge.poll(); // 트럭을 다리에서 내리고,
            currentTime ++; // 시간이 흐른다.

            if(isValidIndex){
                int nextWeight = truck_weights[nextIndex];
                if(weight >= currentWeight + nextWeight){ // 다음으로 갈 트럭이 있다면,
                    bridge.add(nextWeight); // 트럭이 다리위로 올라가고
                    currentWeight += nextWeight; // 다리 위의 무게가 올라간다.
                    if(truck_weights.length -1 < nextIndex + 1) isValidIndex = false; // 모든 트럭이 올라갔다면 더 시도하지 않도록 한다.
                    else nextIndex++; // 아직 남아있다면 커서를 다음으로 옮긴다.
                }else{
                    bridge.add(0); 
                    // 올라갈 트럭은 아직 남아있으나 무게가 초과된다면
                    // 무게 0의 허수를 넣어 시간의 흐름을 구현한다.
                }
            }
            //더 이상 트럭이 없다면 아무것도 넣지않는다.
            
        }
        return currentTime; // 다리 위가 빈 후 시간을 반환한다.

    }
}

 

사실 이 문제를 보고 가장 먼저 어렴풋 떠오른 방법은, 해시를 사용하는 방법이다.

일단은 그래도 출제자의 의도를 맞춰볼까? 하고 풀긴했지만, 해시로도 풀어보고 싶었다.

 

그래서 해시로 시간의 흐름은 어떻게 구현할것이냐?

while문으로 시간을 계속해서 더하고, 트럭을 다리에 올릴때 (현재시간 +다리의 길이) 만큼을 더해서 저장해둔다.

그리고 해당 시간이 되면, 데이터를 지우고 다리위 무게를 다시 줄여서

마치 다리에서 내려온 것과 같은 효과를 내도록 한다.

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        
        truckMap = new HashMap<>();

        int currentTime = 0;
        int currentIndex = 0;
        int currentWeight = 0;
        boolean noTrucksLeft = false;

        while(!noTrucksLeft || !truckMap.isEmpty()){ // 올릴 트럭이 없고, map이 빌 때 까지.
            currentTime++;
            currentWeight -= truckMap.getOrDefault(currentTime, 0); // 현재시간에 다리에서 내려와야 하는 트럭의 무게를 뺀다.
            truckMap.remove(currentTime);	//map에서 삭제한다.

            if(!noTrucksLeft){
                int currentTruck = truck_weights[currentIndex];
                if(weight >= currentWeight + currentTruck){
                    truckMap.put(currentTime + bridge_length, currentTruck);
                    currentWeight += currentTruck;

                    if(currentIndex + 1 > truck_weights.length - 1) noTrucksLeft = true;
                    else currentIndex ++;
                }
            }

        }
        
        return currentTime; // 다리 위가 빈 후 시간을 반환한다.

    }
}

 

아무래도 이쪽이 훨씬 아름다운 풀이인 듯 싶다.

계속해서 데이터를 삽입하는 과정도 없을 뿐더러, 조건문도 덜 복잡해서 이해하기도 쉽다.

아무래도 풀이방법을 제안해주지 않는선에서는, 내 직관을 조금은 믿어봐도 좋을 듯 싶다.