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

klean·2020년 10월 2일

문제풀이 알고리즘 큐 프로그래머스

프로그래머스

목록 보기

1/1

프로그래머스 - 다리를지나는트럭 문제풀이 글입니다

갠적으로 알고리즘 문제 풀이 포스트가 처음입니다.
지적 환영하지만 비난은 자제해주세요

문제설명

트럭이 1차선에 서있음 주어진 순서가 바뀌는 일은 없음(끼어들기 금지)
한 순간에 견딜 수 있는 무게 주어짐
트럭은 1초에 한 칸 움직이며 다리 길이 주어짐

아이디어

전체 트럭이 한 대씩 들어오는 반복문을 만들고 다리를 큐로 만든다.

반복문에선
넣을 수 있는 트럭이 있다->먼저 빠질 트럭이 있다면 빼줌(타임워프)->넣음
넣을 수 있는 트럭이 없다->트럭 하나를 빼줌(타임워프)

풀면서 헤맸던 점

첫 제출 땐 트럭이 들어갈 수 있다면 빠질 수 있는 트럭이 있는지 확인 안 해보고 걍 넣었는데 이 때 70퍼센트 통과가 나왔다.
원인을 🧸🧸히 생각해보니 당시 다리가 무게를 버티길래 왕창 push해두고 나중에 무게를 못버티게 됐을 때가 돼서야 pop 하는데 이 때 마지막 push보다 더 이른 시간으로 타임워프 할 수도 있다.
(예를 들면 길이 2짜리, 무게 30짜리 다리인데 1초에 1번차, 2초에 2번차, 3초에 3번차, 4초에 4번차를 push해 뒀는데 뒤늦게 pop이 나와서 1번차가 빠질 때 3으로 타임워프하고 3초에 5번차를 push하게 된다. 차의 순서가 역전돼버렸다.)

후기

다른 분들 코드 보니까 1초마다 뺄 수 있는 차, 넣을 수 있는 차를 다 검사해도 통과 받으신 것 같아서 괜히 삽질했다는 생각을 해따...
그리고 나는 먼저 케이스를 2개로 나눠서(넣을 수 있는가? 아닌가?) 둘 다 차를 뺄 수 있는지 검사를 했는데 이 검사를 먼저 하고 넣을 수 있을 때만 넣는 것도 가능해보인다.(아직 안해봤어요) 트럭을 빼는 부분이 3군데나 있는데(ㅎ...ㅋ..)함수화라도 해볼걸 싶다.

코드

취향상 다리에 진입하고자 하는 트럭 대기열도 큐로 만들었다.
취향상 pair가 first second가 헷갈려서(...) 트럭 구조체를 만들엇다.

#include <string>
#include <vector>
#include<queue>
#include<iostream>

using namespace std;
struct truck{
    int w,s;//무게, 진입시간
    truck(int ww, int ss){
        w = ww;
        s = ss;
    }
};
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    queue<int> big_q;//대기 트럭
    queue<truck> q;//다리라고 하면
    int cur_w = 0;//현재다리위 무게
    int acc_t = 0;//누적시간
    for(int i =0;i<truck_weights.size();i++){
        big_q.push(truck_weights[i]);
    }
    
    acc_t++;
    while(!big_q.empty()){
        if(cur_w+big_q.front()<=weight){
            //push truck to bridge
            //먼저 하차할 트럭이 있는지 체크하기
            truck front_truck = q.front();
            if(front_truck.s+bridge_length==acc_t){
                q.pop();
                cur_w-=front_truck.w;
            }
            truck new_truck = truck(big_q.front(),acc_t);
            big_q.pop();
            q.push(new_truck);
            
            acc_t++;//1초 지남, 다른 트럭 올 수 있게 됨
            cur_w+= new_truck.w;
            cout<<"After push : "<<cur_w<<","<<acc_t<<","<<new_truck.w<<","<<new_truck.s<<endl;
        }
        else{
            //트럭 더 못넣고 뽑기
    
            truck front_truck = q.front();
            q.pop();
            int dt = bridge_length-(acc_t-front_truck.s);
            acc_t+=dt;
            cur_w-=front_truck.w;
            cout<<"after pop : "<<cur_w<<","<<acc_t<<","<<front_truck.w<<","<<front_truck.s<<endl;
        }
    }
    while(!q.empty()){//다리 위 트럭 쭉 빼줌
        truck front_truck = q.front();
        q.pop();
        int dt = bridge_length-(acc_t-front_truck.s);
        acc_t+=dt;
        cur_w-=front_truck.w;
        cout<<"after pop : "<<cur_w<<","<<acc_t<<","<<front_truck.w<<","<<front_truck.s<<endl;
    }
    
    
    answer = acc_t;
    return answer;
}

klean

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