Lv.2 - 다리를 지나는 트럭 (스택/큐)

안녕하세요. 좋아요요정입니다!

프로그래머스 다리를 지나는 트럭 문제를 풀었습니다 :) 예! 

 

---

Lv.2 - 다리를 지나는 트럭

링크

문제 설명

- 트럭 여러대가 일차선 다리를 정해진 순으로 건넙니다. 모든 트럭이 건너는 최소 시간을 알아내보세요.

- 다리는 한방향으로 이동가능하고 먼저 들어온 트럭이 먼저 나갑니다.

- 다리는 정해진 무게와 길이가 있습니다. 무게=총 올라갈 수 있는 트럭의 무게이고, 길이는 총 올라갈 수 있는 트럭의 수입니다.

 

입력값

- bridge_length : 다리의 이동거리(and 최대 올러갈 수 있는 트럭의 수)

- weight : 다리가 견딜 수 있는 총 무게

- truck_weights : 다리를 건너려는 트럭 무게의 배열

 

제한 조건

bridge_length, weight, truck_weights는 1이상 10,000이하

truck_weight 배열의 값은 1이상 weight 이하

 

 

 

먼저 계획을 해봅시다! 수두코드 작성

1. 다리 링크드 리스트 생성.
   1. 다리는 다리의 길이만큼 트럭이 올라갈 수 있는 다리를 생성합니다.
   2. 다리의 handleTruck() 메서드는 start에 새로운 다리노드를 추가하고, 마지막 다리노드를 삭제합니다.
      마지막에 트럭이 있을 경우 반환합니다. (에스컬레이터 느낌)
   3. 다리의 setTruck()메서드는 입력받은 truck의 무게를 가지는 Truck 객체를 생성해 다리의 start노드에 올립니다.
2. truck_weight[0]부터 반복
3. 다리를 handleTruck()합니다. 한칸씩 이동, 반환되는 트럭이 있을 경우 outlist에 추가합니다.
4. 다리의 현재 무게와 새로 올라갈 트럭의 무게를 더해 다리가 견딜 수 있는지 확인합니다.
   견딜 수 있으면 트럭을 setTruck(), start에 추가합니다. 트럭이 올라가면 index ++ 가 됩니다.
5. truck_weight의 마지막 요소까지 다리에 올라가면 반복문이 종료됩니다.
   (truck_weight[index]가 가리키는 요소가 없으면 반복문이 종료됨)
6. 마지막 트럭이 올라갈 때 까지의 counter와 마지막 트럭이 이동하는 길이 즉 다리의 길이를 합하면 답이 됩니다. 

  

먼저 작은 요소부터 생성해봅니다.

class BridgeNode {
    constructor() {
        this.truck = null;
        this.next = null;
    }
}
class Truck {
    constructor(weight) {
        this.weight = weight;
    }
}

다리의 노드는 트럭을 가지고 다음 노드를 가리킵니다.

트럭은 무게를 가지고 있습니다.

 

 

 

class Bridge {
    constructor() {
        this.start = null;
        this.end = null;
        this.weight = null;
        this.now_weight = 0;
        this.length = null;
    }
}

다리는 시작노드와 끝노드, 견딜 수 있는 무게와 현재 무게, 총 길이를 갖습니다.

 

 

class Bridge {
    constructor() {...}
    
    initBridge(bridge_length, weight) {
        this.weight = weight;
        this.length = bridge_length;
        const newNode = new BridgeNode(0);
        this.start = newNode;
        this.end = newNode;
        for(let i = 1; i < bridge_length; i++) {
            const newNode = new BridgeNode();
            this.end.next = newNode;
            this.end = newNode;
        }
    }
}

initBridge 메스드를 생성해줍니다.

다리의 총 길이와 무게를 입력받아서 입력받은 길이만큼 다리에 노드를 생성해줍니다.

 

 

	setTruck(weight) {
        const newTruck = new Truck(weight);
        this.start.truck = newTruck;
        this.now_weight = this.now_weight + newTruck.weight;
    }

그리고 setTruck메서드를 생성해줍니다.

setTruck메서드는 무게를 받아서 새로운 트럭을 생성한 뒤 start 트럭에 트럭노드는 올려주고, 현재 무게에 트럭의 무게를 더해줍니다.

 

 

    handleTruck() {
        let prev = new BridgeNode();
        prev.next = this.start;
        let temp = this.start;
        let next = this.start.next;
        for(let i = 1; i < this.length-1; i++) {
            temp = next;
            next = temp.next;
        }
        this.start = prev;
        temp.next = null;
        this.end = temp;
        if(next && next.truck) { 
            this.now_weight = this.now_weight - next.truck.weight; 
            return next.truck;
        }
        return null;
    }

 그리고 handleTruck메서드를 생성해줍니다.

칙칙폭폭 트럭을 등에 올린 컨테이너와 같은 구조입니다.

앞에 새로운 노드를 추가하고 마지막 노드를 삭제함으로써 다리가 한칸씩 이동한 듯이 동작합니다.

새로 생성한 빈 노드를 앞에 붙혀주고, 마지막 노드 이전까지 이동을 해줍니다.

마지막 노드 이전의 next를 null값으로 변경해 마지막 노드와의 연결을 끊어주고 마지막 노드에 트럭이 있을 경우 트럭의 무게만큼 현재 무게에서 빼준 뒤 트럭을 반환해줍니다. 

연결이 끊킨 노드는 가비지컬렉터에 의해 제거됩니다.

 

 

모든 준비는 끝이 났습니다. 

function solution(bridge_length, weight, truck_weights) {
    const bridge = new Bridge();
    const outlist = [];
    let counter = 0;
    let index = 0;
    bridge.initBridge(bridge_length, weight);
    
    while(truck_weights[index]) {
        counter++;
        const out = bridge.handleTruck();
        if(out) { 
            outlist.push(out)
        };
        if(bridge.weight >= bridge.now_weight + truck_weights[index]) {
            bridge.setTruck(truck_weights[index]);
            index++;
        }
    } 
    return counter + bridge.length;
}

1. 다리를 생성해줍니다. 

2. 다리의 이동을 저장할 counter 변수와 다리 대기트럭을 하나씩 입력할 때 필요한 index 변수를 생성합니다.

3. 다리를 입력받은 길이와 무게로 init 해줍니다. 

4. 대기트럭이 없을 때까지 반복문을 돌립니다.

    5. 카운터를 증가하고

    6. 다리를 한칸씩 이동합니다.(handleTruck())

    7. 다리를 건넌 트럭은 반환됩니다. 

    8. 다리가 견딜수 있는 무게와 현재 올라가 있는 무게 + 새로 올라가야할 트럭의 무게를 확인한 후 견딜 수 있으면 다리위에 진입시킵니다. (setTruck)

    9. index로 다음 대기트럭을 가리킵니다.

10. 모든 트럭이 올라가면 반복문이 종료됩니다.

11. 마지막 올라간 트럭이 out되려면 다리의 길이만큼 더 지나가야 합니다.  counter와 다리의 길이를 더한 값을 반환합니다.

 

 

🤩🤩🤩 꺄우~!! 

 

문제 상 반환되는 트럭 배열은 필요가 없습니다.

outlist, out을 삭제하면 코드가 좀 더 깔끔해집니다. 

전체 코드는 깃허브에 업로드해두었습니다. 

GitHub - Baejiu/study__withTeamLoverDuck: 자바스크립트, 자료구조 스터디 - 팀러버덕

 

 

 

JavaScript 스터디 팀 러버덕과 함께 합니다.