[코딩테스트] Programmers - 다리를 지나는 트럭 (실패)

 

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

프로그래머스

 

 

풀이

이번 문제는 문제를 이해하는데 엄청 오래 걸렸다. 2시간 넘게 풀었지만 통과하지 못했다. 

 

 

코드 1 - 오답

public class 다리를_지나는_트럭
{
    public int solution(int bridge_length, int weight, int[] truck_weights)  {
        int answer = 0;
        Queue<int> queue = new Queue<int>(bridge_length);
        
        for(int i = 0; i < truck_weights.Length; i++)
        {
            if(truck_weights[i] + queue.Sum() <= weight && queue.Count < bridge_length) 
            {
                queue.Enqueue(truck_weights[i]);
                answer += (bridge_length); // 건너는 시간 
            }
            else
            {
                // answer += ((queue.Count * bridge_length) + queue.Count);
                // answer += ((queue.Count * 1) + queue.Count);
                // answer += ((queue.Count * 1) + 1);
                // answer += ((weight / queue.Count) + 1);
                queue.Clear();
                // answer += 1; // 지나는 시간 

                queue.Enqueue(truck_weights[i]);
                answer += (bridge_length); // 건너는 시간 
            }
        }
        
        // if(queue.Count > 0)
        //     answer += ((queue.Count * bridge_length) + queue.Count);
            // answer += ((queue.Count * 1) + queue.Count);
            // answer += ((queue.Count * 1) + 1);
            // answer += ((weight / queue.Count) + 1);
        
        return answer;
    }

    static void Main(string[] args)
    {
        다리를_지나는_트럭 p = new 다리를_지나는_트럭();

        int bridge_length = 100;
        int weight = 100;
        int[] truck_weights = {10,10,10,10,10,10,10,10,10,10};

        Console.WriteLine(p.solution(bridge_length, weight, truck_weights));
    }
}

 

시간을 한번에 계산하는 식이 문제인 것 같다. 

 

 

코드 2 - 정답

using System;
using System.Collections.Generic;
using System.Linq;

public class 다리를_지나는_트럭
{
    public int solution(int bridge_length, int weight, int[] truck_weights) 
    {
        int answer = 0;
        Queue<int> bridge = new Queue<int>();
        
        // 처음에는 다리 길이만큼 빈 공간(0)을 채워 넣습니다. (컨베이어 벨트 세팅)
        for (int i = 0; i < bridge_length; i++)
        {
            bridge.Enqueue(0);
        }
        
        int current_weight = 0; // 현재 다리 위의 총 무게를 실시간으로 추적
        int truck_idx = 0;      // 출발할 트럭의 인덱스
        
        // 모든 트럭이 다리를 통과할 때까지 반복
        while (truck_idx < truck_weights.Length)
        {
            answer++; // 1초가 흐릅니다.
            
            // 1. 다리의 맨 끝에서 트럭(또는 0)이 나갑니다.
            current_weight -= bridge.Dequeue();
            
            // 2. 새 트럭이 들어올 수 있는지 검사합니다.
            if (current_weight + truck_weights[truck_idx] <= weight)
            {
                // 들어올 수 있다면 트럭을 진입시키고, 무게를 더해줍니다.
                bridge.Enqueue(truck_weights[truck_idx]);
                current_weight += truck_weights[truck_idx];
                truck_idx++; // 다음 트럭을 대기시킵니다.
            }
            else
            {
                // 무게 초과로 못 들어온다면, 다리를 전진시키기 위해 빈 공간(0)을 넣습니다.
                bridge.Enqueue(0);
            }
        }
        
        // 마지막 트럭이 다리에 '진입'하면서 while문이 끝납니다. 
        // 그 마지막 트럭이 다리를 완전히 '통과'하는 데 걸리는 시간(다리 길이)을 더해줍니다.
        return answer + bridge_length;
    }
}

 

시간에 대한 정보가 없어서 어떻게 풀지도 잘 모르겠고 도저히 혼자서 못 풀 것 같아 llm에게 물어봤다. 

길이가 bridge_length인 큐를 만들고, 이 큐에 트럭을 넣으면서 시간을 계산하는 것 같다.