문제설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.
현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.제한 사항
- bridge_length는 1 이상 10,000 이하입니다.
- weight는 1 이상 10,000 이하입니다.
- truck_weights의 길이는 1 이상 10,000 이하입니다.
- 모든 트럭의 무게는 1 이상 weight 이하입니다.
My solution
// 💡 문제 분석 💡
// 스택/큐 문제 : 선입선출 -> 큐 -> 일단 배열 -> 시간복잡도 확인후 linked list로 풀어보기
// in : 최대트럭수(자연수), 견디는무게(자연수), 트럭별무게(자연수배열), out : 최소소요시간(num)
// bridge_length 는 최대 올라갈수 있는 트럭수이자, 다리 길이
// 건너려면 다리길이 1마다 1초씩 필요 -> 다리길이 = 다리 건너는데 걸리는 소요시간 = 최대 트럭수(-> 배열길이)
// 트럭이 다리에 진입하고(push) bridge_length 초 뒤에 완전히 지나감(shift)
// 1초가 한 루프
// 다리를 지난 트럭이 처음 받은 대기트럭과 개수가 같으면 로직 끝남
// 큐 배열을 만들어서 풀거면, 시간을 젤 필요없고, 배열을 push, shift 해주면 됨
// 한 루프에서 판별 : 최대개수, 최대무게, 남은거리
function solution(bridge_length, weight, truck_weights) {
let answer = 0;
const bridge = new Array(bridge_length).fill(0); // 다리 건너는 상황
const finish = []; // 완료한 트럭
const num = truck_weights.length; // 총 트럭수
let remain = weight; // 남은 무게체크
while (finish.length !== num) {
const f_truck = bridge.shift(); // 한칸씩이동
if (f_truck !== 0) { // 트럭이라면 완료배열로 이동하고, 남은 무게에서 다시 더해주기
remain += f_truck;
finish.push(f_truck);
}
if ((remain - truck_weights[0]) >= 0) { // 현재 대기트럭이 추가 가능 무게라면
remain -= truck_weights[0];
bridge.push(truck_weights.shift()); // 대기열에서 다리로 이동
} else { // 불가능 무게
bridge.push(0);
}
answer++;
}
return answer;
}💻 문제 소요시간 : 문제해석, 방향찾기(20m) / 코드작성(30m)
다리 길이만큼의 큐배열을 만들어줘서, 트럭들이 큐배열을 한칸씩 이동하는 방법 이렇게 코드를 짜면, 큐배열에 남는공간이 너무 많아지고, 결국 shift를 수행할때마다 그만큼 쓸데없는 로직이 수행된다. 남은 거리를 직접체크하는 방법으로 큐배열의 낭비를 줄이는 코드로 변경해봤다.
// 다리 건너는 상황부터 count로 남은 거리 체크해줘서 shift 시키기
function solution(bridge_length, weight, truck_weights) {
let answer = 0;
let bridge = [];
let remain_t = bridge_length;
let remain_w = weight;
let num = truck_weights.length; // 총 트럭수
while (num > 0) {
if (bridge.length) {
bridge = bridge.map((o) => { // 한칸씩 이동
return {t: o.t, dist: --o.dist};
});
if (bridge[0].dist === 0) { // 첫번
const out = bridge.shift();
remain_t++;
remain_w += out.t;
num--;
}
}
if ((remain_w - truck_weights[0]) >= 0 && remain_t > 0) { // 가능상황
const truck = truck_weights.shift();
bridge.push({t: truck, dist: bridge_length}); // 대기열에서 다리로 이동
remain_w -= truck;
remain_t--;
}
answer++;
}
return answer;
}bridge 배열에 각 트럭의 무게와 다리를 건너는데 남은 거리를 객체로 넣는방식이다.
한칸씩 이동할때마다, 남은거리(dist)를 하나씩 감소시켜준다.
...
효율성면에서 많이 좋아진거는 같았는데...
여전히 시간이 많이든다.. 엄청많이 소요되는 테스트도 존재한다ㅠㅠ
linked list 로 풀어야하는건가..?
Others
// #1.
function solution(bridge_length, weight, truck_weights) {
// '다리'를 모방한 큐에 간단한 배열로 정리 : [트럭무게, 얘가 나갈 시간].
let time = 0, qu = [[0, 0]], weightOnBridge = 0;
// 대기 트럭, 다리를 건너는 트럭이 모두 0일 때 까지 다음 루프 반복
while (qu.length > 0 || truck_weights.length > 0) {
// 1. 현재 시간이, 큐 맨 앞의 차의 '나갈 시간'과 같다면 내보내주고,
// 다리 위 트럭 무게 합에서 빼준다.
if (qu[0][1] === time) weightOnBridge -= qu.shift()[0];
if (weightOnBridge + truck_weights[0] <= weight) {
// 2. 다리 위 트럭 무게 합 + 대기중인 트럭의 첫 무게가 감당 무게 이하면
// 다리 위 트럭 무게 업데이트, 큐 뒤에 [트럭무게, 이 트럭이 나갈 시간] 추가.
weightOnBridge += truck_weights[0];
qu.push([truck_weights.shift(), time + bridge_length]);
} else {
// 3. 다음 트럭이 못올라오는 상황이면 얼른 큐의
// 첫번째 트럭이 빠지도록 그 시간으로 점프한다.
// 참고: if 밖에서 1 더하기 때문에 -1 해줌
if (qu[0]) time = qu[0][1] - 1;
}
// 시간 업데이트 해준다.
time++;
}
return time;
}
와.. 똑같이 시간이 흐르는 것을 중점으로 뒀지만, 다리에 트럭이 꽉찼는데 별다른 변경없이 시간만 보내는 부분을 if문을 통해 한번에 땡겨줬다.
확실히 시간복잡도가 확 줄어들었다!!
// #2.
function Node(firstData) {
this.data = firstData;
this.prev = null;
this.next = null;
}
// first out last in
function Queue() {
this.first = null;
this.last = null;
this.enqueue = function(node) {
if (this.first === null) {
this.first = node;
this.first.next = node;
this.last = node;
this.last.prev = node;
} else if (this.first === this.last) {
this.first.prev = null;
this.first.next = node;
this.last = node;
this.last.prev = this.first;
this.last.next = null;
} else if (this.last !== null) {
var temp = this.last;
temp.next = node;
this.last = node;
this.last.prev = temp;
}
}
this.dequeue = function() {
var returnValue = this.first.data;
if (this.first === this.last) {
this.first = null;
this.last = null;
} else if (this.first !== this.last) {
this.first = this.first.next;
}
return returnValue;
}
this.length = function() {
if (this.first === null)
return 0;
else if (this.first === this.last) {
return 1;
} else if (this.first !== this.last) {
var count = 1, node = this.first;
while (node.next !== null) {
node = node.next;
count++;
}
return count;
}
}
this.sum = function() {
if (this.first === null)
return 0;
else if (this.first === this.last) {
return this.first.data;
} else if (this.first !== this.last) {
var count = this.first.data !== -1 ? this.first.data : 0, // 이 문제에 맞게 추가함
node = this.first;
while (node.next !== null) {
node = node.next;
if (node.data !== -1) // 이 문제에 맞게 추가한 조건문
count += node.data;
}
return count;
}
}
}
function solution(bridge_length, weight, truck_weights) {
var answer = 0, truck_length = truck_weights.length,
q = new Queue(), end = 0;
var i = 0;
for (; i < bridge_length; i++)
q.enqueue(new Node(-1));
while (end !== truck_length) {
// move truck
answer++;
end += q.dequeue() !== -1 ? 1 : 0;
// add truck
q.enqueue(new Node(q.sum() + truck_weights[0] <= weight ? truck_weights.shift() : -1));
}
return answer;
}정석적인 큐로 푼 답인데, 시간복잡도는 내 풀이와 비슷했다.
Reference
공부중인 개발자