102. 다리를 지나는 트럭

 

기본 틀 :

 

using System;

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

 

위 문제를 풀어보면서 아직까지

 

'어떤 자료구조로 어떻게 알고리즘을 구현해서 문제를 해결할 것인가'

 

라는 생각하는 힘이 많이 약하다는 것을 많이 깨달았다...

 

Stack이나 Queue를 사용해서 제시된 예시는 모두 통과했지만

 

전체 테스트에서 부분적인 통과 밖에 못 했다...

 

인터넷을 통해 다른 사람들의 풀이를 살펴 본 결과

 

        // 다리를 건너는 자동차 Queue
        Queue<int> processCar = new Queue<int>();
        // 현재 다리 위 자동차 무게
        int currentWeight = 0;
        // 시간
        int time = 0;

 

사용하여 다리 위를 건너는 자동차(Queue), 현재 다리 위 자동차 무게(int), 시간(int)

 

로 자료를 만들어주고

 

        foreach(int truck in truck_weights)
        {
            while(true)
            {
                // 진행 중인 차량 수가 다리 길이와 같으면
                if(processCar.Count == bridge_length)
                    // 가장 앞에 있는 차량 제거 및 무게 뺴주기
                    currentWeight -= processCar.Dequeue();
                
                // 현재 다리 위 무게, 다리 위로 올라가기 시도 중인 차량
                // 의 합이 무게 제한을 넘지 않으면
                if(currentWeight + truck <= weight)
                {
                    // 다리 위에 추가
                    processCar.Enqueue(truck);
                    currentWeight += truck;
                    time++;
                    break;
                }
                else
                {
                    // 가짜 차량 추가(기존 다리 위 차량 한 칸 이동 표현)
                    processCar.Enqueue(0);
                    time++;
                }
            }
        }

 

foreach 문으로 매개변수 truck_weights(대기 중인 차량들)을 순서대로 조회 하면서

 

현재 다리의 상태에 따라 해당 차량을 처리해줬다.

 

                // 진행 중인 차량 수가 다리 길이와 같으면
                if(processCar.Count == bridge_length)
                    // 가장 앞에 있는 차량 제거 및 무게 뺴주기
                    currentWeight -= processCar.Dequeue();
                
                // 현재 다리 위 무게, 다리 위로 올라가기 시도 중인 차량
                // 의 합이 무게 제한을 넘지 않으면
                if(currentWeight + truck <= weight)
                {
                    // 다리 위에 추가
                    processCar.Enqueue(truck);
                    currentWeight += truck;
                    time++;
                    break;
                }
                else
                {
                    // 가짜 차량 추가(기존 다리 위 차량 한 칸 이동 표현)
                    processCar.Enqueue(0);
                    time++;
                }

 

다리 위를 진행 중인 차량의 수가 다리의 길이와 같아진다면 맨 앞 차량을 제거(다리 다 건넘)으로 해준다.

 

제한 무게를 초과하지 않을 경우 대기 중인 차량을 Queue에 추가시켜 다리를 건너는 중으로 만들어준다.

 

반대로, 제한 무게를 초과인 상태라면 무게가 0인 차량을 Queue에 추가해 기존 차량들이 한 칸 이동하도록 만들어줬다.

 

        // 마지막 트럭이 다리를 다 건너는 시간 추가
        return time + bridge_length;

 

 

마지막으로 대기 중인 마지막 트럭이 다리를 건너는 시간을 추가해주면

 

우리가 원하는 결과를 얻을 수 있었다.

 

(

 

다른 사람의 코드와 유사하게 접근을 했지만 무게가 0인 자동차를 추가해

다리 위 차량을 한 칸 씩 이동시키는 방법은 생각하지 못 했다.

 

)