🔎 문제
🧩 구현과정 및 코드
개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.
사용할 데이터 구조와 풀이 방향성
적용할 알고리즘 혹은 메서드
수영
구현
- 큐
코드
정답
function solution(length, weight, trucks) { const bridge = new Array(length).fill(0) let time = 0 while (bridge.length) { bridge.shift() // 대기 트럭이 있으면 if(trucks.length) { const sumWeight = bridge.reduce((a, b) => a + b, 0) // 다리에 건널 수 있는지 체크 if (sumWeight + trucks[0] <= weight) { // 건널 수 있으면 bridge.push(trucks.shift()) } else { // 건널 수 없으면 bridge.push(0) } } time++ } return time }
첫 코드(미해결)
function solution(length, weight, trucks) { const bridge = [] let sumWeight = 0; let time = 0 // 초기화(첫 트럭 다리 건너기) sumWeight += trucks[0] bridge.push(trucks.shift()) time++ while (sumWeight) { // 다리에 있던 트럭이 다리를 빠져나옴 sumWeight -= bridge.shift() time++ // 같은 시간에 트럭 1대가 건널 수 있는 경우(길이, 무게 체크) if (bridge.length + 1 <= length && sumWeight + trucks[0] <= weight) { sumWeight += trucks[0] bridge.push(trucks.shift()) } } return time }
정은
구현
코드
function solution(bridge_length, weight, truck_weights) { let time = 0; let weightsOnBridge = 0 const trucksOnBridge = [] // [트럭무게, 이 트럭이 나갈 시간]을 담은 배열 while(truck_weights.length || trucksOnBridge.length) { time++ //맨 앞 트럭이 나갈 시간이면 빼준다 if (trucksOnBridge[0] && time === trucksOnBridge[0][1]) { const outTruck = trucksOnBridge.shift() weightsOnBridge -= outTruck[0] } //트럭을 더 실을 수 있다면 올린다 if (weightsOnBridge+truck_weights[0] <= weight) { const addedTruckWeight = truck_weights.shift() trucksOnBridge.push([addedTruckWeight, time+bridge_length]) weightsOnBridge += addedTruckWeight } //트럭을 올릴 수 없다면, 맨 앞 트럭이 나가는 시간으로 시간이동 else if (weightsOnBridge[0]){ time = weightsOnBridge[0][1]-1 // 다음 턴에서 시간이 증가할걸 대비해서 -1 } } return time }
종혁
구현
- 트럭들은 onBridge라는 큐에 [무게 , 나가는 시간]으로 들어옴다리 무게를 초과하지 않게 트럭이 들어오면서 -> 시간은 1초씩 증가
- 만약 제일 앞에있는 트럭의 나가는 시간과 현재 시간이 같다면 , 앞에 트럭 shift()
- 트럭이 무게를 초과했다면 -> 제일 앞에 있는 트럭은 본인의 나가는 시간에 어차피 제일 먼저 나가게 되어있으므로 현재 시간을 해당 트럭의 나가는 시간으로 바꾼다음, 내보내면 됨
- 트럭이 나갈 때는 bridge_sum 감소
코드
function solution(bridge_length, weight, truck_weights) { let time = 0 let m = 0 const onBridge = [] let bridge_sum = 0 while(truck_weights.length || onBridge.length){ //대기하는 트럭과 현재 이동중인 트럭 모두 없어야함 if(onBridge[0] && onBridge[0][1] === time){ // 현재 onBridge에서 제일 앞에 있는 트럭의 나가는 시간이 현재시간과 동일할시 내보내기 - 이거 없으면 통과X const [kg,_] = onBridge.shift() bridge_sum -= kg } if(bridge_sum + truck_weights[0] <= weight){ // 대기중인 트럭이 다리에 오를 수 있는 경우 const truck = truck_weights.shift() onBridge.push([truck,time + bridge_length]) bridge_sum += truck time ++ // 이경우 시간은 1초씩 증가 } else{ // 트럭이 더 이상 들어올 수 없는 경우 현재시간을 onBridge 제일 앞의 트럭이 나가야하는 시간이라고 바꿔버림 if(!onBridge[0]){continue} const [kg,passingTime] = onBridge.shift() time = passingTime bridge_sum -= kg } } return time + 1 } // onBridge time [ [ 7, 2 ] ] 1 [] 2 [ [ 4, 4 ] ] 3 [ [ 4, 4 ], [ 5, 5 ] ] 4 [] 5 [ [ 6, 7 ] ] 6 [] 7
재웅
구현
코드
function solution(bridge_length, weight, truck_weights) { let time = 0; const truck_amount = truck_weights.length const bridge = new Array(bridge_length).fill(0) const crossed = [] while(crossed.length!==truck_amount){ // 다리를 건너는 트럭 배열의 인덱스와 다리에 있는 시간 인덱스를 동기화시켜야 할 듯 함 // 의식적으로 인덱스를 맞추려하지 않아도 되고, shift, push만 같이 해주면 될 듯 time++ const pop = bridge.shift() if(pop!==0) crossed.push(pop) // 용량 허용치면 대기 트럭을 다리에 추가 // 허용치가 아니면 0을 다리에 추가 const weightSum = bridge.reduce((a,b)=>a+b) if(weightSum + truck_weights[0] <= weight){ bridge.push(truck_weights.shift()) }else{ bridge.push(0) } } return time; }
✏️ 후기
문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.
수영
- 정답 코드에서는 미리 0으로 초기화해준 배열을 먼저 선언한다는 점, 대기 트럭이 들어갈 수 없으면 bridge.push(0)을 해준다는 점에서 차이가 있었다.
- 문제는 이해했으나 구현 과정이 어려웠다.
정은
- 구현 문제에 더 가까운 느낌을 받았습니다
- 문제 이해 능력과 구현 능력을 키워야 할 것 같습니다 😞
종혁
- 통과는 했지만 아직도 이해하지 못한 부분이 존재하는것같다.
재웅
트럭을 인덱스로 밀어서 계산을 해야 된다고 접근한 부분에서 시간을 꽤 소요한 것 같습니다.