알고리즘/c++ 프로그래머스

[프로그래머스 다리를 지나는 트럭] c++ (풀이,코드)

말린밴댕이_공부 2023. 6. 8. 21:43
반응형

문제 링크

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제

 

풀이 및 코드

변명이라면 변명이지만 최근 자격증 공부와 기말고사 공부로 인해 이번 다리 건너기도 굉장히 뇌빼고 푼 경향이 없지 않아 있다고 생각합니다.

 

우선 저의 풀이는 이러합니다.

 

다리를 지나는 트럭

bridge_length대 올라갈 수 있으며 다리는 weight이하까지 무게를 견딤 (완전히 안오르면 무시)

1. 처음 지나갈때 계속 push_back을 해줌 
2. 이제 길이가 다 찼으면 하나씩 vector에서 맨 앞을 erase하면서 원소를 추가시켜줌
   1) 무게가 안된다? 0 push_back + answer++;
   2) 무게가 된다? 트럭 무게 push_back + answer++;
3. 마지막 트럭이 오게되면 그것에 대해서 길이만큼 다리의 길이만큼 push_back을 하고 끝

 

결국 1초를 지났다는것을 반복문을 계속 돌리면서 answer++을 해주는 건데요. 

 

#include <string>
#include <vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int bridge_weight = 0;
    int idx = 0;
    vector<int> bridges;
   
    while(1){
        if(idx == truck_weights.size()){
            answer += bridge_length;
            break;
        }
        answer++;
        if(bridges.size() == bridge_length){
            bridge_weight -= bridges[0];
            bridges.erase(bridges.begin());
        }
       
        if(bridge_weight + truck_weights[idx] <= weight){
            bridge_weight += truck_weights[idx];
            bridges.push_back(truck_weights[idx]);
            idx++;
        }else
            bridges.push_back(0);
    }
    return answer;
}

 

결국 길이가 차기 전 초반에 대해서 일단 다 push_Back을 계속 해줍니다.

 

이제 길이가 다 찼다는 것은 이제 첫 차가 지나간 다음의 환경을 얘기하겠죠

그때는 차의 무게에 대해서 0혹은 존재하는 무게에 대해서 나오게 될겁니다.

 

그것에 대해서 이제 vector의 맨 앞단을 지워줍니다.

 

만약에 마지막 차가 이제 다리에 탔다는 것은 이제 지나가기만 하면 되는것이니 다리의 길이만큼 더해주고 바로 break를 해줍니다.

 

솔직히 이 문제는 제 풀이가 너무 마음에 들지 않는 급박하게 짰으므로 다른분 코드를 참조하시는 것을 추천드립니다.

 

#include <iostream>
#include<algorithm>
#include <functional>         // greater 사용 위해 필요  
#include <vector>
#include<queue>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int count = 0;
    int Time = 0;
    int Truck_weight = 0;
    queue<pair<int, int>> truck_move;

    while (true)
    {
        if (weight >= Truck_weight + truck_weights.at(count))
        {
            truck_move.push(make_pair(truck_weights.at(count), bridge_length + 1 + Time));
            Truck_weight += truck_weights.at(count);
            count++;
        }

        if (count >= truck_weights.size())
        {
            answer = truck_move.back().second;
            break;
        }
        else
        {
            Time++;
            if (truck_move.front().second == Time+1)
            {
                Truck_weight -= truck_move.front().first;
                truck_move.pop();
            }
        }

    }

    return answer;
}

다른 부느이 풀이 코드입니다. 

반응형