D+30 기능개발 js + Stack Queue 직접 구현

문제

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항
작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
작업 진도는 100 미만의 자연수입니다.
작업 속도는 100 이하의 자연수입니다.
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
progresses speeds return
[93, 30, 55][1, 30, 5] [2, 1][95, 90, 99, 99, 80, 99] [1, 1, 1, 1, 1, 1][1, 3, 2]

내 풀이

두 번째 풀이 : Queue가 사실 필요없기에 제거하고 반복문 1번으로 해결하는 방법

function solution(progresses, speeds) {
    const q = [];
    let maxDay =Math.ceil((100 - +progresses[0]) / speeds[0]) 
    let answer =[]
    let count =1;
    
    for(i=1; i<progresses.length; i++){
        const curDay = Math.ceil((100 - +progresses[i]) / speeds[i]) 
        if(curDay<=maxDay)
            {
                count++; 
            }
        else{
             answer.push(count); 
                 count = 1; 
                 maxDay=curDay;
        }
    }
    answer.push(count);
    return answer;
}

(1) Queue를 직접 구현

Queue를 한 번 이용해 보고 싶었다.!
이 방법은 배열을 이용해서 푼 방법

class Queue {
    constructor() {
        this.rear =0;
        this.front =0;
        this.items=[];
    }
    push(val){
        this.items[this.rear]=val
        this.rear++
    }
}
function solution(progresses, speeds) {
    const q = new Queue();
    let maxDay
    let answer =[]
    let count =0;
    
    for(i=0; i<progresses.length; i++){
        const restDay = Math.ceil((100 - +progresses[i]) / speeds[i]) 
        q.push(restDay)
    }
    maxDay=q.items[0];
    for(j=0; j<q.items.length; j++){
        if(q.items[j]<=maxDay)
            {
                count++; 
            }
        else{
             answer.push(count); 
                 count = 1; 
                 maxDay=q.items[j];
        }
    }
    answer.push(count);
    return answer;
}

stack & Queue 직접 구현하는 코드

이 구현의 장점:

• 메모리 효율적 관리
• 상수 시간 O(1) 연산
• 대용량 데이터 처리에 적합
• 명확한 인터페이스 제공

이 구현을 사용하면 10만건, 100만건의 데이터도 효율적으로 처리 가능하다고 한다.

// 최적화된 Queue 구현
class Queue {
    constructor() {
        this.items = {};
        this.head = 0;
        this.tail = 0;
    }
    
    // 요소 추가
    enqueue(element) {
        this.items[this.tail] = element;
        this.tail++;
    }
    
    // 요소 제거 및 반환
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const item = this.items[this.head];
        delete this.items[this.head];
        this.head++;
        return item;
    }
    
    // 첫 번째 요소 확인
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.head];
    }
    
    // 큐가 비어있는지 확인
    isEmpty() {
        return this.tail - this.head === 0;
    }
    
    // 큐의 크기 반환
    size() {
        return this.tail - this.head;
    }
    
    // 큐 초기화
    clear() {
        this.items = {};
        this.head = 0;
        this.tail = 0;
    }
}

// 최적화된 Stack 구현
class Stack {
    constructor() {
        this.items = [];
        this.top = -1;
    }
    
    // 요소 추가
    push(element) {
        this.top++;
        this.items[this.top] = element;
    }
    
    // 요소 제거 및 반환
    pop() {
        if (this.isEmpty()) {
            return undefined;
        }
        const item = this.items[this.top];
        delete this.items[this.top];
        this.top--;
        return item;
    }
    
    // 최상위 요소 확인
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.top];
    }
    
    // 스택이 비어있는지 확인
    isEmpty() {
        return this.top === -1;
    }
    
    // 스택의 크기 반환
    size() {
        return this.top + 1;
    }
    
    // 스택 초기화
    clear() {
        this.items = [];
        this.top = -1;
    }
}