이전 스택/큐 문제에 이어서 바로 다음 문제를 풀어보았습니다.
체감상 난이도가 level2.5급 이었던 그런 문제입니다. 2시간 가까이 걸렸네요;;
목차
0. 문제 설명
트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.
예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
| 경과 시간 | 다리를 지난 트럭 | 다리를 건너는 트럭 | 대기 트럭 |
| 0 | [] | [] | [7,4,5,6] |
| 1~2 | [] | [7] | [4,5,6] |
| 3 | [7] | [4] | [5,6] |
| 4 | [7] | [4,5] | [6] |
| 5 | [7,4] | [5] | [6] |
| 6~7 | [7,4,5] | [6] | [] |
| 8 | [7,4,5,6] | [] | [] |
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
0.0. 제한 조건
- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.
0.1. 입출력 예
| bridge_length | weight | truck_weights | return |
| 2 | 10 | [7,4,5,6] | 8 |
| 100 | 100 | [10] | 101 |
| 100 | 100 | [10,10,10,10,10,10,10,10,10,10] | 110 |
1. 풀이 과정
문제 이해는 금방 했습니다만 알고리즘을 만들어 내는 과정이 참 힘들었습니다.
이게 괜히 시간을 줄이려고 시간을 점프하려고 하니까 더 어렵게 느껴지더군요.
그래서 1시간 반쯤 고민하고 나서 포기하고 시간을 점프하지 않고 하나하나 다 거치게 만들었습니다.
그랬더니 생각보다 금방 풀리더군요.
먼저 어떤 변수가 필요할 것인지에 대해서 생각했습니다.
문제를 보자마자 이건 queue로 풀어야 겠다는 생각을 해서 바로 queue 변수를 만들어줬고
몇 초 후에 각 트럭이 다리를 통과하는 지에 대한 정보를 담고 있는 queue도 필요할 것 같아서 넣어줬습니다. (이 부분은 map으로 pair처리해서 풀 수 있지 않을까 싶기도 합니다)
올라가 있는 트럭의 무게는 int형 변수 w로, 현재 시간은 int형 변수 answer로, 다음에 진입할 트럭의 인덱스를 int형 변수 idx로 두었습니다. 그리고 truck_weights의 size도 미리 구해서 int형 변수 size에 넣어두었습니다.
그 다음에 어떻게 진행할까 고민하다가 예시에서 진입한 차가 없는 순간 알고리즘이 종료되는 것을 확인하고 q.empty()가 만족할 때까지 계속 돌아가도록 while문을 작성했습니다. 이를 위해서는 첫 트럭이 이미 진입한 상태여야 했기 때문에 answer(시간), w, idx를 조정했습니다.
while문 안에는 트럭이 도착했을 때의 알고리즘과 트럭이 새롭게 들어올 때의 알고리즘을 구현했습니다. 각각 q와 q_pop에 값들을 넣거나 빼고 w를 조정해주고, 입장하면 idx를 다음으로 조정해주는 코드만 넣었습니다.
그리고 맨 마지막에 시간이 1씩 증가하도록 ++answer을 넣어서 마무리했습니다. 시간을 마지막에 증가시킨다는 것도 생각해내기 꽤나 어려운 관문이었습니다.
다 완성 시키고 나서 보니 중간에 비는 시간을 단축시킬 방법이 떠올라서 바로 추가했습니다. 조금 더 효율적인 모습을 보여줍니다. (아래 코드로 첨부합니다!)
2. 소스 코드
2.0. 전체 시간을 다 훑는 방법
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0; // 시간
queue<int> q;
queue<int> q_pop;
int idx = 0;
q.push(idx);
q_pop.push(bridge_length);
++idx;
++answer;
int w = truck_weights[0]; // 현재 다리 위 트럭 무게
int size = truck_weights.size();
while(!q.empty()){
if (q_pop.front() == answer){ // 트럭 도착 확인
q_pop.pop();
w -= truck_weights[q.front()];
q.pop();
}
if (idx != size && weight - w >= truck_weights[idx]){ // 트럭 입장 확인
q.push(idx);
q_pop.push(answer+bridge_length);
w += truck_weights[idx];
++idx;
}
++answer;
}
return answer;
}
2.1. 보다 효율적인 방법 (시간 생략)
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
int answer = 0; // 시간
queue<int> q; // 진입한 트럭의 index를 담은 큐
queue<int> q_pop; // 트럭이 통과하는 시간을 담은 큐
int w = truck_weights[0]; // 올라가있는 트럭의 무게
++answer; // 시간 1부터 시작
int idx = 1; // 현재 인덱스 (1부터 시작)
int size = truck_weights.size(); // truck_weights의 크기
q_pop.push(bridge_length); // 첫 트럭이 통과하는 시간을 q_pop에 넣어줌
q.push(0); // q에 첫 트럭이 진입했다는 것을 알려주기 위해 0을 넣어줌
while (!q.empty() && w != 0) {
// 중간에 비는 시간 단축
if (weight - w < truck_weights[idx]) { // 더이상 다리에 트럭이 올라갈 수 없다면
answer = q_pop.front(); // q_pop에 가장 먼저 들어가있는 친구를 answer로 불러옴
}
// 트럭 도착 확인
if (q_pop.front() == answer){
q_pop.pop();
w -= truck_weights[q.front()]; // w에서 빠진 트럭의 무게 빼줌(동시에 q에서 트럭의 index 빼줌)
q.pop();
}
// 트럭 입장 확인
if (idx != size && weight - w >= truck_weights[idx]) {
q.push(idx);
q_pop.push(answer + bridge_length);
w += truck_weights[idx];
++idx;
}
++answer;
}
return answer;
}
3. 후기
Level 2중에서 가장 어려웠던 문제가 아니었을까 하는 생각이 듭니다. 프로그래머스에서 풀었던 문제중에는 카카오 기출문제 다음으로 어려운 수준이었던 것 같네요. 저만 그랬을 수도 있습니다 ㅋㅋㅋㅋㅋ
어려운 문제를 만났을 때는 먼저 시간이 오래 걸리더라도(효율성이 떨어지더라도) 먼저 정확성을 확보하는 답안을 제출하면 효율적인 답을 구하기 쉽다는 교훈을 얻을 수 있는 문제였다고 생각합니다!
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
최근댓글