[JS] 덱(Deque)에 대해서 근데 이제 프로그래머스(구명보트)를 곁들인..

이 문제 풀면서 스택에서 쓰이는 팝, pop과 큐에서 쓰이는 디큐, dequeue가 같이 있을 수 있지 않을까 하는 생각이 들었습니다.

일단 제 입맛대로 만들고 찾다보니..

덱(Deque)이라는 자료 구조가 이미 있더라구요.

간단히 말해서 입출력을 같은 곳에서 하는 스택, 입력(rear)과 출력(front)를 구분해놓은 큐보다 자유도가 높습니다.

front에서 입력과 출력을 할 수 있고, rear에서 입력과 출력을 할 수 있습니다.

 

이게 어떻게 이 문제와 연관되는지 같이 알아보시죠!

---

문제 요약

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

주요 제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• (문제엔 나와있지 않지만..) 효율성 테스트 존재합니다!

 

테스트케이스

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

 

접근 방법

최소한의 왕복으로 모든 사람을 구출하기 위해서는 최대한 limit 무게에 맞춘 쌍을 찾아야될 겁니다.

여러 명이 탈 수 있다는 제한이 있다면 한무 dp라던가, 한무 재귀함수를 했겠지만...... 정말 다행히도 2명씩 탄다는 제한이 있네요(만세!)

 

가장 쉽게 떠올릴 수 있는 생각은 우선 몸무게 순으로 정렬한 다음, 양 끝 값을 합해서 비교하는 과정이겠네요.

 

최소 왕복 알고리즘 순서

1. 몸무게 배열(people)을 오름차순으로 정렬한다,
2. 각 끝 값을 합한 값과 limit을 비교한다,
   1. limit을 넘지 않는다면 pop, dequeue한다.
   2. limit을 넘는다면 pop을 한다.
3. count를 1 늘려준다.

단순히 스택을 쓴다음에 shift나 splice를 쓴다면 효율성 테스트에 걸리게 설계되어있습니다.

pop과 dequeue에 대해서 O(1)인 방법을 찾아내야겠네요.

그래서 아까 말한 덱(deque)이 필요합니다.

 

정답 코드

class StackQueue {
    constructor(queue) {
        this.queue = queue ? queue : [];
        this.front = 0;
        this.rear = queue ? queue.length : 0;
    }
    
    enqueue(val) {
        this.queue[this.rear++] = val;
    }
    
    dequeue() {
        const val = this.queue[this.front];
        delete this.queue[this.front++];
        return val;
    }
    
    pop() {
        const val = this.queue[--this.rear];
        delete this.queue[this.rear];
        return val;
    }
    
    size() {
        return this.rear - this.front;
    }
    
    weight() {
        return this.queue[this.rear - 1] + this.queue[this.front];
    }
}
function solution(people, limit) {
    const sorted = people.sort((a, b) => a - b);
    const queue = new StackQueue(sorted);
    let count = 0;
    while (queue.size() > 0) {
        const weight = queue.weight();
        if (weight <= limit) {
            queue.dequeue();
            queue.pop();
        } else {
            queue.pop();
        }
        count++;
    }
    return count;
}

 

팁 1. rear와 front의 특성에 따른 dequeue와 pop 설계

dequeue() {
    const val = this.queue[this.front];
    delete this.queue[this.front++];
    return val;
}

pop() {
    const val = this.queue[--this.rear];
    delete this.queue[this.rear];
    return val;
}

 

같은 듯 다릅니다. front는 내보내야할 index이기 때문에 값이 들어있지만, rear는 넣어야할 index이기 때문에 비어있습니다. 그래서 서로 index 조정해야하는 방법이 약간 다릅니다. 이런 것만 조심해주면 크게 문제 될 건 없습니다.

(weight 역시 rear의 특성으로 인해 index를 1 빼주었습니다.)

 

 

덱에 대한 이해가 있다면 쉽게 풀릴 수 있는 문제였습니다.

 

그럼 이만!