[C++] 프로그래머스 다리를 지나는 트럭

programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

 

1. 서론

 

큐로 푸는 문제! 답만 맞으면 되기야 하는 세상이지만... 이렇게 푸는 게 맞나 싶다.

 

2. 문제 풀이

 

트럭이 다리를 건너간다. 트럭은 1초에 길이 1씩 움직이며, 다리 위에 올라갈 수 있는 트럭의 하중이 정해져 있다. 

모든 트럭이 다리를 다 건넜을 때 걸리는 시간은 몇 초인지를 구하는 문제다.

 

굉장히 심플해 보이지만 '어떻게 한 개의 트럭이 다리를 다 지나는지를 알 수 있을까?' 이 부분에서 굉장히 고민했다.

처음에는 트럭마다 변수를 줘서 트럭이 다리를 다 지났는지 체크하는 용도로 사용하려고 했는데 아무리 생각해도 아닌 것 같아서 생각한 방법은 큐에 0을 넣어주는 것이다. 하중 때문에 대기가 있을 때 0을 넣어 큐에서 트럭을 이동시키는 것이다.

트럭과 0을 넣다보면 큐가 다리의 길이만큼 차게 되니 그때 pop을 해주면 하나의 트럭이 다리를 지났다고 보는 것이다.

 

문제의 예시로 설명하자면 이렇다.

 

7, 4, 5, 6kg의 트럭이 있는 경우

 

1초 7

2초 7 0

3초 0 4

4초 4 5

5초 5 0

6초 0 6

7초 6 0

8초 0 0

 

총 8초가 걸린다.

 

하중 때문에 넣을 수 없는 경우는 0을 대신 넣어줘서 트럭이 이동하는 것처럼 큐에서 이동시켜 pop 해준다.

8초에 모든 트럭이 다 지나가고 큐에 0만 남았기 때문에 답을 return 해준다. 

 

고뇌에 찬 모습

 

3. 코드 설명

 

#include <queue>
#include <vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, i = 0, x = 0, f = 0;
    queue<int> q, t;
    
    while(1) 
    {
        answer++;
        if (q.size() == bridge_length)
        {
            x -= q.front();
            q.pop();
        }
        
        if (i == truck_weights.size())
        {
            if(q.front() == 0 && q.back() == 0)
            {
                t = q;
                while(!t.empty())
                {
                    if (t.front() == 0)
                        t.pop();
                    else
                    {
                        f = 1;
                        break;
                    }
                }
                if (t.empty())
                    break;
            }
            q.push(0);
        }
        else
        {
            if(x + truck_weights[i] <= weight)
            {
                q.push(truck_weights[i]);
                x += truck_weights[i];
                i++;
            }
            else
                q.push(0); 
        }
    }
    
    return answer;
}

 

난 왜 항상 논리는 간단하고 코드는 더러운 걸까... ㅠ

 

변수 x는 다리의 현재 하중을 나타낸다. 변수 f는 큐의 모든 수가 0으로 가득 찼는지 판별하기 위해 사용한다.

i는 truck_weights 배열의 index다. 배열의 한 항씩 보면서 다리에 올라갈 수 있는 하중이 되는지 판별하게 된다.

만약에 다리에 올라갈 수 있으면 q에 넣고 올라갈 수 없으면 0을 넣어준다. 그리고 만약 큐의 길이가 다리의 길이와 같아지게 되면 pop 앞의 트럭을 pop 해준다.

이 작업을 반복하다가 truck_weights 배열이 한 바퀴를 다 돌고 나면 큐의 모든 값이 0으로 가득 찼는지 확인해준다.

이때 임시 큐 t를 이용해 pop 하며 큐 값에 0이 아닌 값이 있으면 아직 다리를 다 빠져나오지 못한 트럭이 있는 것이기 때문에 큐에 0일 다시 넣어주고, 큐의 모든 값이 0이면 반복문을 빠져나온다.