[자바스크립트] Queue 문제들

🌱 큐(Queue) 란 ?
먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식의 자료구조

🔗 자바스크립트로 큐 구현하기

분명 전에 한 번 구현해보고 문제도 많이 풀었었는데,
어떻게 잠깐 알고리즘 공부 쉬었다고 이렇게 초멘나사이가 됐지...? 😭
다시 매일 꾸준히 하자!! 🔥

문제1. 🔗 프로그래머스 다리를 지나는 트럭

경과	시간	다리를 지난 트럭	다리를 건너는 트럭 대기 트럭
0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

표를 보고 알 수 있는 내용

• 대기 트럭이 다리로 입차할 때 경과되는 시간은 무시한다
• 다리에 있는 차량 출차 후 입차가 진행된다
  • 3초 대에, 7kg 차량이 나가고 4kg 차량이 다리에 바로 올라올 수 있었다.

풀이1. Queue로 간단히 풀기

1. 다리 위에 차량도 없고, + 대기 중인 트럭이 없을 때까지 반복한다

   • 시간은 while 문을 1번 도는 동안 1초씩 지나간다
   • 다리 위 차량들의 위치도 모두 한 칸 앞으로 간다

2. 입차 조건 : 대기 중인 트럭이 있고 + 다리 위 트럭무게 총합 + 입차하려는 차량의 무게 <= 다리가 버틸 수 있는 무게일 때

   • 입차 : 대기중인 차량 목록(배열)의 가장 첫 번째 차량을 .shift() 해서,
     - bridge[] 배열에 넣고 (위치 0)
     - 다리 위 차량 무게 총합에도 더한다

3. 출차 조건 : 다리 위에 차량이 있고 + 다리 위에 있는 차량 중 가장 첫 번째 차량의 위치가 다리의 길이와 같을 때

   • 출차 : 다리 배열의 가장 첫 번재 요소를 꺼내고 .shift(),
     - 다리 위 차량 무게 총합에서도 해당 차량의 무게를 뺀다

function solution(bridge_length, weight, truck_weights) {
    let time = 0, bridge = [], totalWeights = 0
    
    while(bridge.length > 0 || truck_weights.length > 0){
        time++
        
        // 다리 위의 모든 차량 위치 +1 이동 // [위치, 무게] = bridge[i]
        for(let i = 0; i < bridge.length; i++){
            bridge[i][0]++
        }
        
        // 출차
        if(bridge[0] && bridge[0][0] >= bridge_length){
            let [_, truckWeight] = bridge.shift()
            totalWeights -= truckWeight
        }
        
        // 입차
        if(truck_weights.length && weight >= totalWeights + truck_weights[0] ){
            let truck = truck_weights.shift()
            bridge.push([0, truck])
            totalWeights += truck
        }
    }
    return time 
}

풀이2. class로 신기한(?) 풀이

---

문제2. 🔗 백준 1158 요세푸스 문제

1차 도전 : splice로 풀기

입력이 7 3 일 때 출력이 <3, 6, 2, 7, 5, 1, 4> 로 나와야 하는데 <3, 2, 1, 7, 5, 4, 6> 로 나왔다.

1 부터 N 까지 담긴 배열에서 K 번째 숫자를 꺼낸 후,
꺼내진 숫자로부터 다시 다음 K 번째 숫자를 꺼내야 하는데,
이 때 K번째가 배열의 길이를 넘어갈 때,
어떻게 다시 0번째 인덱스로 넘어갈 지 알고리즘을 짜는게 어려웠다.

계속 출력되는 순서가 안맞아서 splice 풀이법을 포기하고 다른 방법을 찾아봤는데,
풀고나서 다른 사람들의 숏코딩을 보니 splice로 푼 풀이도 있어서 다시 도전해보기로 했다.

let [N, K] = require('fs').readFileSync(0).toString().trim().split(' ').map(Number)

let a = [...Array(N)].map((_, idx) => idx + 1)
let answer = []

while (a.length) {
  let i = --K
  answer.push(a.splice(i, 1)[0])
  i = (i + K) % --N
}

console.log(`<${answer.join(', ')}>`) // <3, 2, 1, 7, 5, 4, 6>

2번차 도전
class 로 원형 likned list를 만들어서 .next() 로 풀어야할 지 고민했는데,
class를 새로 만들어서 풀기에는 풀이가 너무 복잡해질 거 같아서 pass
원형 linked list 구현은 한 번 해봐야겠다고 생각 🔥

🔗 자바스크립트로 원형 linked list 구현

풀이 1. Queue

3번 째 풀이 : Queue 에 담아서 K 번째 숫자가 맞으면 answer에 담고,
아니면 Queue의 맨 뒤로 보내서 숫자가 모두 제거될 때까지 마지막 숫자에서 첫 번째 숫자로 계속 숫자들이 이어지도록 하기

1. 1부터 N까지 숫자를 Queue에 담는다
   N이 7이면 [1, 2, 3, 4, 5, 6, 7]
2. 1번째 부터 K-1 번째 숫자는 K번째 숫자가 아니므로, Que에서 꺼내서 맨 뒤로 push 한다.

• K 번째 숫자 % K === 0 이므로 if(count % K ===0) 으로 조건 작성
• K가 3이면 [3, 4, 5, 6, 7, 1, 2]

3. K번 째 숫자를 Queue에서 꺼내서 answer에 담는다.
4. Queue 에 담긴 숫자가 없을 때까지 반복

let [N, K] = require('fs').readFileSync(0).toString().trim().split(' ').map(Number)

let que = [...Array(N)].map((_, idx) => idx + 1)
let answer = [],
  count = 1

while (que.length > 0) {
  const shiftItem = que.shift()
  if (count % K === 0) {
    answer.push(shiftItem)
  } else {
    que.push(shiftItem)
  }
  count++
}

console.log(`<${answer.join(', ')}>`)

풀이 2. splice

const [N, K] = require('fs').readFileSync(0).toString().trim().split(' ').map(Number)

let arr = [...Array(N)].map((_, idx) => idx + 1)
let pick = 0
let answer = []

while (arr.length) {
  pick = (pick + K - 1) % arr.length 
  answer.push(arr.splice(pick, 1))
}

console.log('<' + answer.join(', ') + '>')

---

추가 문제 모음

🔗 프로그래머스 스택/큐 문제들
🔗 백준 스택/큐/덱 문제들