[JS] 코딩테스트 고득점 Kit - 스택/큐 한번에 정리하기

같은 숫자는 싫어

/*
I:arr [1,1,3,3,0,1,1]
O:answer [1,3,0,1]
C:
배열 arr의 크기 : 1,000,000 이하의 자연수
배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

E: if(arr.length == 1)return arr;

algo: stack
ds: arr

*/

function solution(arr)
{
    var answer = [arr[0]];

    for(let i = 1; i < arr.length; i ++){
        if(answer[answer.length - 1] == arr[i])continue;
        answer.push(arr[i]);
    }

    return answer;
}

기능개발

function solution(progresses, speeds) {
    let answer = [0];
    let days = progresses.map((progress, index) => Math.ceil((100 - progress) / speeds[index]));
    let maxDay = days[0];

    for(let i = 0, dayIdx = 0; i< days.length; i++){
        if(days[i] <= maxDay) {
            answer[dayIdx] ++;
        } else {
            maxDay = days[i];
            answer[++dayIdx] = 1;
        }
    }

    return answer;
}

1. 남은 일수 배열만들기
   (100 - 진행률) / speed 하면 몇일 남았는지에 대한 배열이 만들어지게 됨.
   progresses [93, 30, 55] 와 speeds [1, 30, 5] 배열을 통해서 아래와 같은 배열을 생성한다.

(100 - 93) / 1 = 7이므로 7일 걸리고
(100 - 30) / 30 = 2.xx이므로 3일 걸리고
(100-55) / 5 = 9일 걸림

[7,3,9] 배열이 만들어짐.

 

2. 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다는 설명 참고해 결과 배열 생성하기
   [7,3,9]에서 7일이 지나야 0번째, 1번째 기능을 한꺼번에 배포할수있음.
   (3일이 지나면 1번째 기능을 배포할수있는 상태지만 앞에있는 기능이 배포될때 함께 배포되어야 하기 때문)

쉽게 생각하면 배열을 앞에서부터 뒤로 볼때 점점 숫자가 내려가는 그룹만 모아서 그룹의 길이를 배포한다고 생각하면 됨.

[7,3,9]는 (7,3) (9) 이므로 [2,1]을 반환해야함.

for(let i = 0, dayIdx = 0; i< days.length; i++){
//같이 배포할수있는 것들을 찾기위한 조건문
        if(days[i] <= maxDay) { 
            answer[dayIdx] ++;
        } else {
//맨 앞에 있는 것들이 이미 배포되었고, 새로운 배포 일수를 정하는 조건문
            maxDay = days[i];
            answer[++dayIdx] = 1;
        }
    }

올바른 괄호

function solution(s){
    if(s.length == 1)return false;
    if(s.legnth % 2 == 1)return false;
    let stack = [];

    for(let i = 0; i < s.length; i++){
        if(s[i] == "(")stack.push("(")
        else if(s[i] == ")" && stack[stack.length-1] == "(")stack.pop();
        else return  false;
    }
    return stack == 0 ? true : false;
}

위에는 Stack을 활용한 나의 풀이이고 아래는 stack의 개념을 이용한 간결한 풀이이다.

function solution(s){
    if(s.legnth % 2 == 1)return false;

    let curNum = 0;
    for(let c of s){
        curNum += c == "(" ? 1 : -1;
        if(curNum < 0) return false;
    }
    return curNum ? false: true;

}

첫번째 두번째 풀이 모두 시간복잡도는 O(N)이지만 두번째 풀이는 공간복잡도가 O(1)이다.

효율성은 둘다 비슷한거 보니 마음대로 본인 머리에 맞는거 쓰면 되겠다.

프로세스

function solution(priorities, location) {
    let priorArr = priorities.map((prior,idx)=> [prior,idx]);

    let outNum = 0;
    while(priorArr.length > 0){
        // 현재 큐에서 최대 우선순위 찾기
        let maxNum = Math.max(...priorArr.map(item => item[0]));

        let [priority, index] = priorArr.shift();

        if(priority < maxNum){
            // 우선순위가 최대가 아니면 뒤로 보내기
            priorArr.push([priority, index]);
        } else {
            // 우선순위가 최대면 실행
            outNum++;
            if(index === location) return outNum;
        }
    }
    return outNum;
}

1. 우선순위만 있던 배열에 현 인덱스를 추가
   [우선순위,0], [우선순위, 1] ...과같은 배열을 만든다.
2. while문을 통해서 queue의 로직을 실행한다.
   한번의 while을 거치면 앞에있던게 뒤로가거나, 앞에있던게 사라지거나, 앞에있던게 location과 동일하다는 조건문을 거친뒤 return하거나 총 3개의 결과로 귀결된다.

다리를 지나는 트럭

function solution(bridge_length, weight, truck_weights) {
    let time = 0;
    let curWeight = 0;
    let queue = [[0,0]]; // [나갈시간, 현 무게]

    while(queue.length > 0 || truck_weights.length > 0){
        //1. 현 시간이 나갈시간이 됐으면 무게를 빼주고, 큐에서도 뺀다.
        if(time == queue[0][0]){
            curWeight -= queue.shift()[1];
        }
        //2. 트럭이 들어올수있는 상황이면 트럭 넣어주고, 무게도 추가한다.
        let leftWeight = weight - curWeight;
        if(leftWeight >= truck_weights[0] && bridge_length > queue.length){
            let curTruck = truck_weights.shift();
            queue.push([time + bridge_length, curTruck]);
            curWeight += curTruck;
        }else{
        //맨 앞에있는 애가 밖으로 나갈수있게 시간 점프하기
        if(queue[0])time = queue[0][0] - 1;
        }
        time++;
    }
    return time;
}

주식가격

function solution(prices) {
    const n = prices.length;
    const answer = new Array(n).fill(0);
    const stack = [];

    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && prices[i] < prices[stack[stack.length - 1]]) {
            const j = stack.pop();
            answer[j] = i - j;
        }
        stack.push(i);
    }

    while (stack.length > 0) {
        const j = stack.pop();
        answer[j] = n - 1 - j;
    }

    return answer;
}

예시