[프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 다리를 지나는 트럭

구현 문제

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

 

오래 걸린 문제입니다.

알고리즘 풀이를 많이 해도 구현 문제를 연습하지 않으면 상당히 어렵습니다.

---

[문제 풀이]

 

순서가 정해져 있는 트럭들이 다리를 지나는 데에 걸리는 최소 시간을 구하는 문제입니다.

 

다리의 특징은 먼저 들어간 트럭이 먼저 나와야 한다는 것입니다. 여기서 우리는 큐를 떠올려야 합니다.

이제부터 다리를 큐라고 생각하겠습니다.

 

어떻게 풀이해야 하는지 한 번에 감이 오지 않습니다.

그러므로 해야 하는 작업을 나눠서 생각해보겠습니다.

 

1. 새로운 트럭이 다리에 들어올 때, 다리의 용량이 버틸 수 없다면 새로운 트럭이 지나갈 수 있을 때까지 다리 위의 트럭들을 건너 보냄
2. 새로운 트럭이 다리에 들어올 때, 다리의 용량이 버틸 수 있다면 바로 새로운 트럭을 투입

2번의 경우는 처리하기 간단합니다. 시간을 1초 늘리고 큐에 트럭을 한 대 넣으면 됩니다.

현재 시간을 기록하는 변수를 하나 만들어서 2번의 경우마다 시간을 1 증가시키고 큐에 트럭을 넣으면 됩니다.

 

문제는 1번의 경우입니다.

다리 위의 트럭들을 건너 보내는 작업을 하나씩 해주면 참 편하겠지만 트럭의 개수 N이 최대 10,000개이고 다리의 길이 L이 최대 10,000입니다.

$O(NL)$의 시간 복잡도를 가지므로 100,000,000번이나 트럭을 보내주는 작업을 해야 합니다. 다른 방법을 생각합시다.

 

이 문제를 해결하기 위해 시간을 최대한 스킵해야 합니다.

1번의 경우, 현재 들어올 트럭의 무게를 버틸 수 있을 때까지 다리 위의 트럭을 제거하고, (마지막으로 제거된 트럭이 다리에 진입한 시간 + 다리의 길이)로 시간을 이동한다면 1, 2번 과정을 전부 $O(N)$에 처리할 수 있습니다.

다리의 길이를 더해주는 이유는 트럭이 1초당 1만큼 움직이므로 다리의 길이가 곧 트럭이 다리를 지나가는 시간입니다.

 

위의 시간을 스킵하는 과정에서 (마지막으로 제거된 트럭이 다리에 진입한 시간)이 필요하므로 트럭마다 진입한 시간을 넣어야 합니다.

그리고 현재 다리 위의 트럭의 무게 합을 확인하기 위해 트럭의 무게도 기록해둬야 합니다.

즉, 큐에는 클래스(구조체) 타입의 원소를 넣겠습니다.

큐를 두 개 만들어서 각각 시간과 무게를 기록해도 괜찮습니다.

 

이때, 다리 위의 트럭 무게 합을 빠르게 변경하기 위해 트럭의 무게 합을 저장해야 하는 변수를 하나 만들어 줍니다.

 

 

위의 과정으로 과연 답을 도출할 수 있을까요?

프로그래머스에서 제시한 예제는 위의 과정만 구현해도 정답을 받을 수 있습니다.

그러나 실제로 채점을 한다면 오답을 받게 됩니다.

 

생각해보면 2번의 경우에서 문제가 생길 것 같지는 않습니다.

트럭을 한 대 집어넣고 시간을 1초 늘리는 과정은 매우 직관적인 풀이이기 때문입니다.

 

1번 과정에서 시간을 최대한 스킵했는데, 다리 위의 트럭을 제거하는 과정이 조금 미심쩍습니다.

만약 다리의 길이가 2이고 용량이 11일 때, [5, 5, 1, 1]와 같은 입력이 들어온다고 가정합시다.

위의 과정을 그대로 이행한다면

 

경과 시간	다리를 지난 트럭	다리를 건너는 트럭		대기 트럭
0	[]	[]		[5, 5, 1, 1]
1	[]	[5]		[5, 1, 1]
2	[]	[5, 5]		[1, 1]
3	[]	[5, 5, 1]		[1]
3	[5]	[5, 1, 1]		[]
5	[5, 5, 1, 1]	[]		[]

이렇게 됩니다.

 

표가 이상해 보인다면 매우 정상입니다. 하지만 오타는 없습니다.

왜 위와 같은 현상이 발생했을까요?

 

이 문제가 발생한 원인은 다리의 길이를 고려하지 않았기 때문입니다.

처음으로 3초에 도달했을 때, 다리를 건너는 트럭의 개수가 3개입니다.

그러나 다리의 길이가 2라서 다리를 건너는 트럭의 개수가 최대 2개여야 합니다.

 

용량에는 문제가 없으므로 다리 위에 트럭을 그냥 올렸는데, 올려놓고 보니 가장 처음에 들어간 용량 5의 트럭이 자연스럽게 나갈 수 있게 된 것입니다.

하지만 자연스럽게 나가는 트럭을 고려하지 않아서 (마지막으로 제거된 트럭이 다리에 진입한 시간 + 다리의 길이) = 1 + 2 = 3이 되었고, 그로 인해 시간을 스킵한 결과가 다시 3초가 된 것입니다.

 

3초라는 시간이 두 번이나 나온 이유가 바로 이것입니다.

 

이 문제를 해결하기 위해서 모든 반복문에서 트럭을 다리에 올려놓기 전에, 자연스럽게 나갈 수 있는 트럭이 있는지 확인해주면 됩니다.

(다리의 가장 앞에 있는 트럭이 다리에 진입한 시간 + 다리의 길이)가 현재 시간과 같은지 확인하고 같다면 큐에서 트럭을 한 대 빼주면 됩니다.

 

이 과정을 추가해서 위의 예제를 다시 확인해보면 아래와 같이 나옵니다.

 

경과 시간	다리를 지난 트럭	다리를 건너는 트럭		대기 트럭
0	[]	[]		[5, 5, 1, 1]
1	[]	[5]		[5, 1, 1]
2	[]	[5, 5]		[1, 1]
3	[5]	[5, 1]		[1]
4	[5, 5]	[1, 1]		[]
5	[5, 5, 1]	[1]		[]
6	[5, 5, 1, 1]	[]		[]

 

이제 위의 내용을 총 정리하자면

 

• 필요한 변수는 현재 시간, 무게 합에 대한 변수
• 다리의 역할은 큐가, 트럭은 큐에 들어가는 원소
• 트럭에 대한 정보는 진입한 시간과 트럭의 무게를 묶은 클래스(구조체)
• 큐에 들어가고 나갈 때마다 무게 합 변수에 무게를 더하고 뺌
• 다리의 용량이 부족하다면 트럭들을 제거하고 (마지막에 제거된 트럭이 다리에 진입한 시간 + 다리의 길이)로 시간 이동
• 다리의 길이를 고려해서 나갈 수 있는 트럭은 바로 나가게 하기

분야가 스택/큐로 되어 있어 큐를 사용하였지만, 두 포인터를 사용하여 풀이하는 것이 더 직관적이라고 생각합니다.

 

---

[소스 코드] / C++

 

구현에 비해 코드는 간단하니 코드를 이해하는 것도 좋습니다.

 

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

using namespace std;

class Truck {
public:
    int w, t;
    
    Truck (int w, int t) {
        this->w = w;
        this->t = t;
    }
    
    ~Truck() {}
};

int solution(int len, int weight, vector<int> truck_weights) {
    int currentTime = 0, sum = 0;
    queue<Truck> q;
    
    for (int tw : truck_weights) {
        if (q.size() > 0 && currentTime - q.front().t == len) {
            sum -= q.front().w;
            q.pop();
        }
        
        Truck pre = Truck(0, 0);
        while (sum + tw > weight) {
            pre = q.front();
            sum -= pre.w;
            q.pop();
        }
        
        if (pre.w > 0) currentTime = pre.t + len;
        else currentTime++;
        
        q.push(Truck(tw, currentTime));
        sum += tw;
    }
    
    return currentTime + len;
}

 

---

[메모]

 

• assign(n, k): 크기가 n이고 k로 채움 / resize(n, k): 크기가 n이고 늘어난 부분만큼 k로 채움