[프로그래머스] 다리를 지나는 트럭 문제 - 자바스크립트 배열, 연결 리스트 두가지 방법으로

 

1. 배열로 접근하는 방법

 

전체 풀이

function solution(bridge_length, weight, truck_weights) {
    // queue 초기화
    let queue = new Array(bridge_length).fill(0);
    let seconds = 0;
    
    while (queue.length) {
        // queue 하나씩 실행
        queue.shift();
        seconds++;
        
        let queueSum = queue.reduce((acc,cur) => acc + cur, 0);
        
        if (truck_weights.length) { 
            if (queueSum + truck_weights[0] <= weight) {
                // 1. 현재 queueSum과 truck_weights[0] 합이 weight보다 같거나 작으면 -> queue에 push();
                let temp = truck_weights.shift();
                queue.push(temp); 
            } else {
                // 2. 현재 queueSum과 truck_weights[0] 합이 weight를 넘으면 -> queue에 push(0)
                queue.push(0);
            }
        }
    }
    
    return seconds;
}

 

(1) queue 초기화해주고 while문에서 queue를 하나씩 실행하면서 맨 앞의 원소를 shift() 해준다.

    let queue = new Array(bridge_length).fill(0);
    let seconds = 0;

 

(2) 현재 다리를 지나는 queue의 트럭의 무게를 합을 구한다.

let queueSum = queue.reduce((acc,cur) => acc + cur, 0);

 

(3) 다리 위 트럭무게에 대기 중인 맨 앞 트럭의 무게를 더한 값을 다리가 버틸 수 있는지 없는지 분기해서 queue에 트럭을 push 할지, 0을 push 할지 판단한다.

        if (truck_weights.length) { 
            if (queueSum + truck_weights[0] <= weight) {
                let temp = truck_weights.shift();
                queue.push(temp); 
            } else {
                queue.push(0);
            }
        }

 

2. 연결 리스트로 구현하기

 

첨부한 이미지를 보면 코드 효율성이 많이 떨어짐을 알 수 있다. 이 문제는 특정 인덱스에 해당하는 노드를 찾을 필요가 없고 FIFO로만 구현하면 되기 때문에 배열보다는 연결 리스트로 푸는 것이 훨씬 효율성 측면에서 좋다.

 

class Node {
	constructor(data) {
    	this.data = data;
        this.next = null;
    }
}

class Queue {
	constructor() {
    	this.head = null;
        this.rear = null;
        this.count = 0;
        this.sum = 0;
    }
    
    enqueue(data) {
    	const node = new Node(data);
        if (this.head) {
        	this.rear.next = node;
        } else {
        	this.head = node;
        }
        
        this.rear = node;
        this.sum += data;
        this.count++;
    }
    
    dequeue() {
    	if (!this.head) {
        	return;
        }
        const data = this.head.data;
        this.head = this.head.next;
        this.count--;
        this.sum -= data;
        return data;
    } 
    
    getFirst() {
    	if (this.head) {
        	return this.head.data;
        } else {
        	return false;
        }
    }
    
    getQueue() {
    	if (this.count === 0) {
        	return false;
        } else {
        	let node = this.head;
            let array = [];
            while (node) {
            	array.push(node);
            	node = node.next;
            }
            return array;
        }
    }
}

 

기본적인 자바스크립트 연결리스트 구현법을 활용하여 큐에 필요한 함수를 정의했다. 먼저 노드 클래스를 정의해 주고, 큐 클래스에는 큐의 초기 형태와 큐에 원소를 추가, 삭제, 반환하는 함수를 만들어줬다. 큐에 들어가 있는 트럭의 무게의 합을 구해야 하므로 enqueue, dequeue 함수에 전체 큐에 올라간 무게까지 연산하는 로직을 추가했다. 참고로 이 문제에서는 반환하는 함수는 필요가 없고 enqueue, dequeue만 있으면 된다. 

 

function solution(bridge_length, weight, truck_weights) {    
    let seconds = 0;
    let queue = new Queue();
    for (let i = 0; i < bridge_length; i++) {
        queue.enqueue(0);
    } 
    
    while (queue.count) {
        queue.dequeue();
        seconds++;
        
        if (truck_weights.length) {
            if (queue.sum + truck_weights[0] <= weight) {
                queue.enqueue(truck_weights.shift());
            } else {
                queue.enqueue(0);
            }
        }
    }
    
    return seconds;
}

위에서 배열로 푸는 방법과 똑같이 풀었다. 배열로 푼 답안을 보고 작성한 결과가 계속 0이 나오길래 엄청 고민해서 원인을 찾았는데, while문에서 queue.length로 참 조건을 판단하고 있었던..;; 덕분에 3시간 동안 삽질했다. 아오..

 

연결 리스트의 효율성은 어마무시했다!