시작하며 🌈

아무래도 리액트로 함수형 프로그래밍을 하다 보니, 클래스를 많이 쓰게 되질 않더군요. 그래서, 알고리즘을 공부하며 클래스를 연습하고 있습니다!
단순히 문제를 해결하는 거보다는, 일단 제가 부족한 부분에 대해서 학습하며 길러나가려 노력하고 있네요.

당장 보이지 않더라도, 언젠간 성장했다는 보람을 느낄 수 있도록 말이죠. 그럼 시작해봅시다!

본론 📃

오늘의 문제는, 다음과 같은 문제였어요.
https://programmers.co.kr/learn/courses/30/lessons/42583#

일단 문제를 딱 처음 볼 때부터, 아 이건 queue문제구나! 싶었습니다.

이 문제를 접했을 때 제 사고는 다음과 같았어요.

[1] 일단 문제를 보면 좀 특이하다. 0초에는 아무것도 없다니!
[2] 생각해보니, 이건 트럭이다. 다리에 완전히 진입하려면, 일단 트럭의 뒤까지 다 들어와야 되니, 결국에는 다리에 완전히 진입하는 시간이 1초가 걸린 것이다!
[3-1] 그러니까 일단 쉽게 계산하려면 들어갈 때 1초가 걸리는 거니까, 처음부터 시간을 더해주면 쉽겠구나.
[3-2] 그 다음에 다리에 있는 트럭들의 시간을 카운트를 1 추가해주고 말야.
[3-3] 그 다음에는 트럭이 다리에서 도착했는지 체크해줘서, 다리 상태를 정리해야겠다!
[4-1] 만약 다리를 지나갈 수 있다면 그냥 큐에 넣어주고
[4-2] 아니라면 다리를 지나갈 수 있을 때까지 다리에 있는 트럭들을 정리해야겠다.
[5] 결국에 큐에서 다 없어지면, 남은 다리에 있는 트럭들만 정리해야겠다.
[6] 결과 반환!

class Queue {
    constructor(arr) {
        this.arr = arr;
    }
    append(val) {
        this.arr.push(val);
    }
    popleft() {
        return this.arr.shift();
    }
    getLength() {
        return this.arr.length;
    }
    getWeight() {
        if (this.arr.length === 0) return 0;
        return this.arr.reduce((acc, cur) => acc + cur[0], 0)
        
    }
    setTime(time) {
        if (this.arr.length === 0) return;
        this.arr.forEach(truck => {
            truck[1] += time;
        })
    }
    checkArrived(length) {
        if (this.arr.length === 0) return;
        if (this.arr[0][1] === length) this.popleft()
    }
    getArrivalTime(length, time) {
        return length - time;
    }
    print() {
        return this.arr
    }
    // 다리의 무게가 다음 트럭이 들어올 때까지 큐를 빼내고 시간을 계산한다.
    setTruckArrivedTime(length, time) {
        const [now, remainingTime] = this.popleft();
        const cost = this.getArrivalTime(length, remainingTime);
        time += cost;
        this.setTime(cost);
        return time;
    }
}

const solution = (bridge_length, weight, truck_weights) => {
    let time =  0;
    const queue = new Queue(truck_weights);
    const bridgeQueue = new Queue([]);
    while (queue.getLength() !== 0) {
        const now_truck_weight = queue.popleft();
        time++;
        bridgeQueue.setTime(1);
        bridgeQueue.checkArrived(bridge_length);

        if (bridgeQueue.getWeight() + now_truck_weight <= weight) {
            bridgeQueue.append([now_truck_weight, 0])
        } else {
            // 다리에 트럭이 올라갈 수 있을 때까지 큐를 빼내고 시간을 측정
            while (bridgeQueue.getWeight() + now_truck_weight > weight) {
                time = bridgeQueue.setTruckArrivedTime(bridge_length, time)
            }
            bridgeQueue.append([now_truck_weight, 0]);
        }
    }
    while (bridgeQueue.getLength()) {
        time = bridgeQueue.setTruckArrivedTime(bridge_length, time)
    }
    return time;
}

마치며 🎉

음... 문제 난이도로 치자면 어려운 문제는 아니었는데, 이해하기가 꽤나 까다로웠어요. 사실상, 어떤 기법보다는 문제 자체에 맞춰 구현하는 것이 훨씬 난이도가 높았던 듯 싶네요.

큐를 두개 쓰면서 관리하는 것도 꽤나 귀찮은... 😂
분명 더 쉬운 방법도 있을 것 같기는 합니다.

방금 구상한 거로는 다음과 같은 설계도 가능할 것 같기도 하네요.

1. 결국에는 순서대로 1초마다 다리를 지나간다고 가정. 그렇다면 결국에는 처음 다리에 완전히 진입하는 트럭 개수 + 다리 길이만큼 시간은 over될 것.
2. 다만 우리가 계속 오차가 나는 이유는 각각의 트럭이 다리를 지나가는 데 필요한 대기시간 때문
3. 대기시간만 따로 구해주는 로직만 있다면 트럭 개수 + 다리 길이 + 각 트럭이 진입하는 데 있어 소요된 대기시간

일단 오늘도 공부할 게 워낙 많아서, 끝나고 자투리 시간에 꼭 해봐야겠습니다!