들어가며

프로그래머스 코딩테스트 고득점 Kit 스택/큐 문제 중 하나인 다리를 지나는 트럭 문제 풀이 후 review를 위한 포스팅입니다.

---

문제 풀이

• 이 문제에서 구해야 하는 것은 트럭이 다리를 지나가는데 걸린 시간입니다. 시간은 어떻게 구해야 할까요?
• 시간이 언제 흐르는 지 알 수 있으면, 그 시점에 시간을 나타내는 변수의 값을 1씩 증가시켜 얼마만큼의 시간이 흘렀는지 알 수 있습니다. 그럼 시간은 언제 흐를까요?
• 시간은 트럭이 다리에 올라갈 때 그리고 트럭이 다리에서 이동할 때 흐릅니다.
• 그럼 트럭은 언제 다리에 올라갈 수 있을까요? 그리고 트럭의 이동은 어떻게 나타낼 수 있을까요?
• 트럭은 다리에 올라갈 트럭이 남아 있을 때, 다리에 올라간 트럭 무게의 합과 다리에 올라갈 트럭 무게의 합이 다리가 지탱할 수 있는 무게를 초과하지 않았을 때 다리에 계속해서 올라 갈 수 있습니다.

우선 필요한 것들을 입력 받아야 겠죠?

우리는 다리의 길이와, 다리가 지탱할 수 있는 무게, 그리고 트럭들의 무게를 입력 받습니다.

이중 트럭들의 무게는 vector로 입력 받습니다.

// 다리의 길이
int bridge_length

// 다리가 지탱할 수 있는 무게
int weight

// 트럭들의 무게
vector<int> truck_weights

입력 받은 트럭들의 무게를 다리에 올라갈 트럭들의 대기줄로 가정하기 위해 vector의 원소들을 queue로 옮깁니다.

// 다리에 올라갈 트럭들의 대기줄
queue<int> truck;

for(int i : truck_weights) {
	truck.push(i);
}

다리에서 트럭은 한쪽에서 다른 한쪽으로 이동하기 때문에 queue를 이용해 구현할 수 있으며, 다리에 올라간 트럭들의 무게를 구하기 위해 변수를 하나 생성하고 0으로 초기화 해줍니다.

// 다리
queue<int> bridge;

// 다리에 올라간 트럭들의 무게
int bridge_weight = 0;

우리가 구해야 하는 것은 트럭들이 다리를 지나가는데 걸리는 시간입니다. 시간을 가정하는 answer 변수도 잊지 말고 초기화 해줍니다.

// 시간
int answer = 0;

필요한 것은 이제 모두 갖춰졌습니다. 이제 시간을 구해 보죠.

모든 트럭들이 다리를 건넜다는 것을 어떻게 알 수 있을까요?
트럭 대기줄과 다리에 트럭이 한 대도 남아있지 않으면 모든 트럭들이 다리를 건넜다고 생각할 수 있습니다.

// 모든 트럭이 다리를 건널 때까지 반복
while(!truck.empty() || !bridge.empty()) {
	...
}

언제 트럭을 다리에 올릴 수 있을까요?
다리가 트럭으로 꽉 차있지 않으면 트럭을 다리에 올릴 수 있지 않을까요?

// 모든 트럭이 다리를 건널 때까지 반복
while(!truck.empty() || !bridge.empty()) {

	// 다리가 트럭으로 꽉 차있지 않으면 트럭을 계속해서 다리에 올린다
	while(bridge.size() < bridge_length) {
    	...
    }
}

하나 잊은게 있습니다. 트럭 대기줄에 트럭이 남아있지 않으면 트럭을 다리에 올릴 수 없겠네요.

// 트럭 대기줄이 비었으면 더 이상 다리에 올릴 트럭이 없다
if(truck.empty()) {
	break;
}

잊은게 또 하나 있습니다. 다리에 올라간 트럭들의 무게와 다리에 올릴 트럭 무게의 합이 다리가 지탱할 수 있는 무게를 초과하지 않으면 다리에 트럭을 올릴 수 있습니다.

// 트럭을 다리에 올릴 수 있으면 올린다
if(bridge_weight + truck.front() <= weight) {
	bridge.push(truck.front());
	bridge_weight += truck.front();
	truck.pop();
}

트럭의 이동은 어떻게 나타낼까요? 트럭을 올릴 수 없을 때는 어떻게 할까요?
다리에 올라간 트럭들의 무게와 다리에 올라갈 트럭의 무게의 합이 다리가 지탱할 수 있는 무게를 초과한 경우 트럭을 다리에 올릴 수 없습니다. 단, 트럭을 다리에 올리지 않더라도 다리에 올라간 트럭은 앞으로 한칸 이동해야겠죠.

현재 다리에 push 되고 있는 것은 다리에 올라가는 트럭들의 무게입니다. 그러면 0을 다리에 push하면 어떻게 될까요?
다리를 나타내는 queue의 길이는 길어지지만 다리에 올라간 트럭들의 무게는 늘어나지 않습니다. 이를 통해 트럭의 이동을 나타낼 수 있습니다.

// 다리에 트럭이 올라갈 수 없는 경우
else {
    bridge.push(0);
}

트럭이 다리에 올라가거나 트럭이 이동할 때 시간은 흐릅니다.

// 트럭이 다리에 올라가거나 트럭이 이동할 때 시간은 흐릅니다.
answer++;

0을 다리에 push 함으로써 이제 다리가 비어있는 경우는 모든 트럭이 다리를 건넜을 때 말고는 없습니다.

// 다리가 비어 있는 경우는 트럭들이 다리를 다 건넜을 때뿐이다.
if(bridge.empty()) {
	break;
}

다리에 올라간 트럭은 언제 내릴까요?
다리가 꽉 찼을 때 트럭을 다리에서 내리면 됩니다.

// 다리가 꽉 차면 다리에서 트럭을 내린다.
bridge_weight -= bridge.front();
bridge.pop();

마지막에 다리에 올라간 트럭이 다리를 지나는 시간을 추가해주면 모든 트럭이 다리를 건너는데 걸리는 시간을 구할 수 있습니다.

answer += bridge_length;

전체 코드 확인

---

마치며

스택과 큐 자료 구조 자체는 단순하지만 자료 구조를 활용한 문제는 아직 어렵게만 느껴지네요.

Reference

• Programmers. 다리를 지나는 트럭.