[프로그래머스] 다리를 지나는 트럭(java)

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 다리를 지나는 트럭

문제해석

순서상 앞에 있는 대기트럭이 먼저 다리를 건너고, 모든 트럭의 속도가 1초에 1로 동일하므로 다리를 건너는 트럭들도 먼저 건너기 시작한 트럭이 먼저 지날 것입니다.

따라서 First In, First Out(FIFO)의 규칙을 가지고 있는 Queue를 활용한다면 쉽게 문제를 해결할 수 있다고 생각하였습니다.

 

풀이

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> standby = new LinkedList<>();
        for(int truck : truck_weights){
            standby.offer(truck);
        }
        Queue<Integer> crossing = new LinkedList<>();
        Queue<Integer> stamp = new LinkedList<>(); 
        
        int time=1, weightSum=0;
        do{
            if(standby.peek()!=null && weightSum+standby.peek() <= weight){
                crossing.offer(standby.peek());
                stamp.offer(time);
                weightSum+=standby.poll();
            }
            time++;
            if( time - stamp.peek() >= bridge_length){
                weightSum -= crossing.poll();
                stamp.poll();
            }
        }while(crossing.peek()!=null || standby.peek()!=null);
        
        return time;
    }
}

다리에 입장하기 위해 필요한 정보는 다리를 건너는 트럭들의 무게 합과 대기 트럭의 무게, 다리를 건너기 위해 필요한 정보는 트럭이 다리에 입장한 후 소요된 시간입니다.

다리를 지난 트럭은 무게 합에서 제외됩니다. 이때 각 트럭의 무게정보가 필요합니다.

대기트럭들의 무게를 담는 standby, 다리를 건너고 있는 트럭들의 무게를 저장하는 crossing, 다리에 입장한 시간을 저장하는 stamp를 모두 Queue 객체로 선언하였습니다.

트럭이 다리에 입장할 수 있다면 대기트럭 Queue에서 제외하고 crossing에 무게를, stamp에 입장한 시간을 저장합니다.

트럭이 지나간 거리는 현재 시간 - 입장한 시간으로 다리 길이보다 길다면 Queue에서 제거하고 루프를 반복합니다.

반복문은 대기 트럭 Queue, 다리에 있는 트럭 Queue가 모두 비어있을때까지 반복됩니다.

crossing과 stamp는 같은 시기에 원소가 추가, 삭제되므로 하나가 비어있다면 다른 하나도 비어있습니다.

대기트럭 Queue와 다리 위의 트럭 Queue가 모두 비어있다면 반복문을 종료하고 경과한 시간을 반환합니다.

 

위의 코드는 분명 테스트를 통과하기엔 충분했지만 다음과 같은 부분이 마음에 들지 않았습니다.

1. 대기 트럭 Queue의 추가로 입력받은 트럭 수만큼 루프가 필요하다는 점

2. 다리 위의 트럭 Queue crossing과 stamp는 트럭의 정보를 나타냄에도 불구하고 별개의 Queue를 사용하였다는 점

개선

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Map<Integer,Integer> crossingMap = new HashMap<>();
        int time=1, weightSum=0, index=0, size=truck_weights.length;
        do{
            if(index<size && weightSum+truck_weights[index] <= weight){
                crossingMap.put(time+bridge_length,truck_weights[index]);
                weightSum+=truck_weights[index];
                index++;
            }
            time++;
            if(crossingMap.containsKey(time)){
                weightSum -= crossingMap.remove(time);
            }
        }while(!crossingMap.isEmpty() || index<size);
        
        return time;
    }
}

3개의 개선사항을 반영한 코드를 작성하였습니다.

대기 Queue 선언, 초기화보다 몇번째 트럭이 입장할 차례인지를 표현하는 int형 변수 index 선언이 공간적으로, 시간적으로 더 효율적이므로 대기 Queue를 제거하였습니다.

HashMap의 Key 값으로 다리를 지나는 시간을, Value 값으로 트럭의 무게를 저장 후 각 시간마다 Map에서 containsKey함수로 찾아 제거함으로서 매 루프마다 시간 계산이 필요없도록 하였습니다.