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

 

 

- 문제 풀이

"큐"를 사용하는 문제였다.

 

 

- 코드

처음 제출한 코드는 다음과 같다.

#include <string>
#include <vector>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    // 필요한 변수 선언
    int answer = 0;
    
    // 중첩 for문을 통해 총 걸리는 시간 계산
    for(int i=0; i<truck_weights.size(); i++) {
        int length_count = 1;
        int weight_count = truck_weights[i];
        for(int j=i+1; j<truck_weights.size(); j++) {
            if( length_count+1<=bridge_length 
                         && weight_count+truck_weights[j]<=weight ) {
                length_count++;
                weight_count += truck_weights[j];
                i++;
            }
            else
                break;
        }
        answer += bridge_length;
        answer += length_count-1;
      }
    answer++;
    
    // 계산 값 반환
    return answer;
}

 

 

하지만 위와 같은 결과가 나왔다.

이를 해결하기 위해 다음과 같이 수정해야 했다.

중첩 for문 대신 큐를 사용했다.

cpu 스케줄링을 하는 원리처럼 다리를 큐로 구현하여 하나씩 지나갈 수 있도록 했다.

큐를 구현하여 최종적으로 제출한 코드는 다음과 같다.

#include <queue>
#include <vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    
    int idx=0;    //차량 지목용 idx
    int sum=0;   //현재 다리에 올라와있는 차량 무게 총합
    queue<int> q;  //현재 다리를 건너는 트럭 체크용 큐
    
    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);  //진입할 수 없다면 0을 푸시해서 시간초 계산
        }
    }
   
    return answer;
}

(코드 참고: https://velog.io/@qhsh866/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Level2-%EB%8B%A4%EB%A6%AC%EB%A5%BC-%EC%A7%80%EB%82%98%EB%8A%94-%ED%8A%B8%EB%9F%AD-C )