[프로그래밍 문제 풀이] 프로그래머스 - 다리를 지나는 트럭 (C#)

 

◎ 문제

 

○ 출처

 

https://programmers.co.kr/learn/courses/30/lessons/42583

 

○ 문제 설명

 

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.   따라서, 모든 트럭이 다리를 지나려면 최소 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 이하입니다.

 

○ 입출력 예

 

 

○ 작성 예시 코드

 

using System;

public class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        return answer;
    }
}

 

---

 

 

◎ 나의 문제 풀이

 

// 각 트럭의 정보를 저장할 클래스
class Truck
{
        public int weight;  // 트럭의 무게
        public int count;   // 현재 트럭이 지나가고 있는 다리길이 (시간)

        public Truck(int w, int cnt)
        {
            weight = w;
            count = cnt;
        }
}

public class Solution
{
        public int solution(int bridge_length, int weight, int[] truck_weights)
        {
            int answer = 0;

            // 다리를 건너기전 트럭 대기열을 저장할 큐
            Queue<int> truck_queue = new Queue<int>(truck_weights);
            // 현재 다리를 건너가고 있는 트럭정보를 저장할 리스트
            List<Truck> bridge_list = new List<Truck>();

            // 현재 다리를 건너는 트럭들의 총 무게
            int current_weight = 0;
            
            while(truck_queue.Count > 0 || bridge_list.Count > 0)
            {
                answer++;

                // 현재 다리를 건너는 트럭들의 시간을 각각 증가 시킨다.

                // 아래 반복문을 실행할 때 i를 0부터 시작해서 순차적으로 실행할 경우,
                // RemoveAt가 실행되면서 반복 조건문에 있는 bridge_list.Count가 감소하여
                // 뒤에 있는 리스트 요소가 정상적으로 삭제되지 않으므로 반드시 역순으로 실행해야 한다.
                for (int i = bridge_list.Count -1; i >= 0; --i)
                {
                    bridge_list[i].count++;     // 각각의 트럭의 시간 증가

                    // 트럭이 다리길이를 통과할 경우 총 다리무게에서 삭감하고 리스트에서도 삭제
                    if (bridge_list[i].count >= bridge_length)
                    {
                        current_weight -= bridge_list[i].weight;
                        bridge_list.RemoveAt(i);
                    }
                }

                if (truck_queue.Count > 0)
                {
                    int temp_weight = truck_queue.Peek();

                    // 현재 다리를 지나는 트럭과 다음 진입할 트럭의 무게가 허용치 이내일 경우,
                    // 다리 총무게에 진입하는 트럭무게를 합산하고 다리를 건너는 트럭리스트에 추가
                    if (current_weight + temp_weight <= weight)
                    {
                        current_weight += truck_queue.Dequeue();

                        Truck temp_truck = new Truck(temp_weight, 0);

                        bridge_list.Add(temp_truck);
                    }
                }
            }

            return answer;
        }
}