M'S Blog

M'S Blog

WWDC20 student challenge Winner!

프로그래머스 - 다리를 지나는 트럭

최대 1 분 소요

문제

프로그래머스 - 다리를 지나는 트럭 풀러가기

문제 분석

이 문제는 큐를 이용해서 특정 무게의 트럭을 추가 할 수 있는지 없는지 파악한 뒤 할 수 있다면 큐에 트럭의 무게를 넣어주고 없다면 그냥 0의 값을 넣어주면 됩니다.

다리의 길이가 10000이하이기 때문에, 시간을 1씩 증가시키면서 진행해도 괜찮습니다.

문제 코드(C++)

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <queue>
     
    using namespace std;
     
    int solution(int bridge_length, int weight, vector<int> truck_weights) {
        int answer = 0;
        
        queue<int> q;
        int idx=0;
        int sum=0;
        
        while(1){
            if(idx == truck_weights.size()){
                answer+=bridge_length;
                break;
            }
            
            answer++;
            
            int tmp = truck_weights[idx];
            
            if(q.size()==bridge_length){
                sum-=q.front();
                q.pop();
            }
            
            if(sum+tmp<=weight){
                sum += tmp;
                q.push(tmp);
                idx++;
            }else{
                q.push(0);
            }
        }
        
        return answer;
    }
    		cs
    • 16~19번째 줄 : 모든 truck이 다리에 올라갔다면, 마지막 트럭의 이동이 끝나기만 하면 됩니다. 따라서 현재 시간에 다리 길이 만큼의 시간을 더해주고 반복문을 끝냅니다.
    • 21~23번째 줄 : 시간을 1올려주고 truck의 무게를 구합니다.
    • 25~27번째 줄 : 큐의 크기가 다리의 크기와 같다면, 이동이 끝난 것이므로 큐에서 해당 트럭과 sum에서 해당 무게를 빼줍니다. 이때, 다리의 끝에 다다른 것이 트럭이 아니라면 무게를 0으로 해서 큐에 삽입 했으므로 sum에는 변화가 없습니다.
    • 30~36번째 줄 : 다리에 트럭을 올릴 수 잇으면 트럭의 무게를 큐에 넣고, 무게 총합에 해당 무게를 더해줍니다. 올릴 수 없다면 큐에 0을 추가합니다.





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고