[프로그래머스] 다리를 지나는 트럭 | C#

[ 다리를 지나는 트럭 ]

 

문제 설명

 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 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]	[5]
6 ~ 7	[7, 4, 5]	[6]	[]
8	[7, 4, 5, 6]	[]	[]

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

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

 

제한 조건

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

 

입출력 예

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]	[5, 6]

 

 

 

[ 풀이 ]

 노트를 놓고 와서 그림판에 그렸다.. ㅎ

첫번째 입출력 예시를 그려봤다. 이렇게 이 문제는 선입선출(FIFO)니까 스택과 큐 중에 큐를 사용해서 풀었다.

 

[ 코드 ]

using System;
// Queue를 사용하기 위해 호출
using System.Collections.Generic;

public class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
    	// Queue 선언 및 초기화
        Queue<int> bridge = new Queue<int>(); 
        
        int time = 0; 
        int curWeight = 0; 
		
        // 트럭 수만큼 반복
        for (int i = 0; i < truck_weights.Length; i++) {
        	// 현재 트럭 무게 = i번째 트럭 무게
            int truckWeight = truck_weights[i];
			
            // 트럭이 큐에 추가될 때까지 반복
            while (true) {
            	// 큐가 가득 찼으면 큐에서 트럭을 제거하고 현재 무게 감소
                if (bridge.Count == bridge_length) { 
                    curWeight -= bridge.Dequeue(); 
                }
                else if (curWeight + truckWeight <= weight) { 
                	// 큐에 트럭 추가하고 현재 무게를 증가.
                    bridge.Enqueue(truckWeight);
                    curWeight += truckWeight; 
                    time++;
                    break;
                }
                // 현재 무게와 트럭의 무게가 weight보다 크다면
                else { 
                	// 큐에 0 추가하고 시간 증가.
                    bridge.Enqueue(0);
                    time++;
                }
            }
        }
		
        // 큐의 길이를 시간에 추가.
        time += bridge_length;

        return time;
    }
}