[프로그래머스 코딩테스트] 다리를 지나는 트럭

코딩테스트 연습 > 스택/큐 > 다리를 지나는 트럭
문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/42583

문제

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간		다리를 지난 트럭	다리를 건너는 트럭	대기 트럭
0				[]				[]					[7,4,5,6]
1~2				[]				[7]					[4,5,6]
3				[7]				[4]					[5,6]
4				[7]				[4,5]				[6]
5				[7,4]			[5]					[6]
6~7				[7,4,5]			[6]					[]
8				[7,4,5,6]		[]					[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_length	weight	truck_weights					return
2				10		[7,4,5,6]						8
100				100		[10]							101
100				100		[10,10,10,10,10,10,10,10,10,10]	110

---

풀이

로직

해당 문제도 먼저 들어온 트럭이 먼저 나가야하는 로직이기때문에 큐를 사용해야 한다. 다음과 같은 로직으로 문제를 해결했다.

• 다리queue와 대기queue를 생성한다.
• 다리queue에 bridge_length 만큼 0을 채워넣어 공간을 마련한다.
• 대기queue에 첫번째 트럭을 다리queue로 옮긴다.
  - 이때, 다리에 있는 트럭의 무게가 weights를 넘지 않는 경우에

풀이

class Queue{
    constructor(){
        this.queue=[];
        this.front=0;
        this.rear=0;
    }
    
    enqueue(value){
        this.queue[this.rear++] = value;
    }
    
    dequeue(){
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front++;
        return value;
    }
    
    peek(){
        return this.queue[this.front];
    }
    
    size(){
        return this.rear - this.front;
    }
}

function solution(bridge_length, weight, truck_weights) {
    let time = 0;
    let weightSum = 0;
    
    const bridge = new Queue();
    const ready = new Queue();
    for(let i=0; i < bridge_length; i++){
        bridge.enqueue(0);
    }
    for (const weight of truck_weights){
        ready.enqueue(weight);
    }
    
    while(ready.size() > 0){
        const currentTruck = ready.peek();
        weightSum -= bridge.dequeue();
        
        if(weightSum + currentTruck <= weight){
            bridge.enqueue(currentTruck);
            weightSum += currentTruck;
            ready.dequeue();
        }else{
            bridge.enqueue(0);
        }
        time++;
        
    }
    return time+bridge_length;
}

문제해결

문제
아래와 같은 코드로 문제를 해결했을때 테스트4, 5에서 시간초과가 발생해 틀렸다.
시간초과가 걸렸다는 것은 로직에는 문제가 없지만 반복되는 요소 때문이라고 판단했다.

    //생략
    
    while(ready.size() > 0){
        const currentTruck = ready.peek();
        bridge.dequeue();
        
        const totalWeight = bridge.queue.reduce((sum, weight) => sum += weight);
        if(totalWeight + currentTruck <= weight){
        
	//생략

해결
다리에 있는 트럭들의 무게를 합하는 부분에서 reduce를 사용하는 부분을 변수 weightSum을 사용하여 계산하는 구조로 변경하여 문제를 해결했다.

	//생략
        weightSum -= bridge.dequeue();
        
        if(weightSum + currentTruck <= weight){
            bridge.enqueue(currentTruck);
            weightSum += currentTruck;
            ready.dequeue();
	//생략

느낀점

큐를 활용하여 알고리즘을 생각해내고, 시간효율성까지 따져볼 수 있는 문제였다. 효율성이 더 높은 코드를 짜기 위해 노력해야지!!