[스택&큐] 프로그래머스 알고리즘 Kit 문제풀이 (JS)

[Lv1] 같은 숫자는 싫어

function solution(arr)
{
    const answer = [arr[0]]; //첫번째 원소는 항상 포함
    
    for(let i=1;i<arr.length;i++){
        if(arr[i]!==arr[i-1]){ //현재와 이전요소와 비교
            answer.push(arr[i])
        }
    }

    
    return answer;
}

정확성: 71.9, 효율성: 28.1

 

🛠 Refactor

 

function solution(arr)
{
    return arr.filter((v,i)=>arr[i]!==arr[i+1])
}

 

정확성: 71.9, 효율성: 28.1

 

[Lv2] 기능개발

function solution(progresses, speeds) {
    var answer = [];
    const work=[]
    //1. 작업일 배열 생성
    for(let i=0;i< progresses.length;i++){
        let left=100-progresses[i];
        left=Math.ceil(left/speeds[i])
        work.push(left)
    }
    //2. 순회
    let deploy=work[0];
    let count=0;
    
    for(let i=0;i<work.length;i++){
        
        if(work[i]<=deploy){
            count++
        }else {
            answer.push(count)
            deploy=work[i];
            count=1;

        }
        //마지막요소일때
        if(i===work.length-1){
             answer.push(count);
            return answer;
        }
    }

}

 

🛠 Refactor

function solution(progresses, speeds) {
    var answer = [];
  
    //1. 작업일 배열 생성
    const work=progresses.map((v,i)=>Math.ceil((100-v)/speeds[i]));
    //2. 순회

    let deploy=work[0];
    let count=0;
    
    for(let i=0;i<work.length;i++){
        
        if(work[i]>deploy){
            answer.push(count);
            count=0;
            deploy=work[i];
        }
        count++;
    }
    answer.push(count); //마지막 요소 push
    return answer;

}

[Lv2] 올바른 괄호

function solution(s){
    let count = 0;
    
    for(let i=0;i<s.length;i++){
       
        if(count<0){
            return false
        }
        if(s[i]==='('){
            count++
        }else {
             count--
           
        }
      
        
    }
      if(count!==0){
            return false
        }
    return true

}

순회를 마쳤을때 count가 0이되었어도 올바른 괄호가 아닐 수 있는데, 

 

- 열린괄호가 모두 닫혀야 새로운 열린괄호가 나오는것은 아니다.

- ✨ 열린괄호가 올바르게 닫혔는지 확인하는 문제이므로, 순회하면서 열린괄호에 비해 더 많은 닫힌괄호가 나와서는 안된다. (음수 체크)

 

🔍 오답 노트

function solution(s){
    let count = 0;
    
    for(let i=0;i<s.length;i++){
       
        if(count<0){
            return false
        }
        if(s[i]==='('){
            count++
        }else {
             count--
            if(s[i+1]==='('){
                if(count!==0){
                    return false
                }
            }
           
        }
      
        
    }
      if(count!==0){
            return false
        }
    return true

}

)닫힌괄호 이후 ( 열린 괄호가 나올때, 이미 괄호가 완성되어야하지 않나 라는 생각으로 if문을 추가했다.

하지만 (()()) 이런 경우에는 조건문에 의해 false가 되는 문제점이 발생한다.

 

🛠 Refactor

 

[Lv2] 프로세스

function solution(priorities, location) {
    let maxPriority=Math.max(...priorities);
    let queue = priorities.map((priority, index) => [priority, index]);
    let answer = 0;
    
    while(queue.length){
        
        let [curPriority,curIndex]=queue.shift();
        if(maxPriority===curPriority) //탈출
        {
            answer++
            if(location===curIndex){ //Location 발견
                return answer;
            }
            maxPriority = Math.max(...queue.map(([priority, _]) => priority));
        } 
        else { //다시 줄서기
            queue.push([curPriority,curIndex]);
        }
    }
    return answer;
}

전체를 순회하지 않고, 해당 location의 index가 큐에서 빠져나갈때 return을 하려면, index를 포함하는 배열(queue)로 새로 만들수밖에 없었다. 

 

✅ maxPriority가 shift된 요소의 우선순위 값이 같은지 기준으로 조건문을 생성했다.

 

큐에서 탈출할때, maxPriority를 새로 업데이트를 해주고, 몇번째로 빠져나가는지는 answer로 카운트해주고, 탈출한 curIndex가 찾고있는 location이면 return 해주면된다.

 

다시 줄을 서야할땐, shift한 요소들을 다시 push해주면 된다.

 

 

🛠 Refactor

function solution(priorities, location) {
    // 각 요소의 원래 인덱스와 함께 튜플을 생성합니다.
    let queue = priorities.map((priority, index) => [priority, index]);
    let answer = 0;

    while (queue.length > 0) {
        let [currentPriority, currentIndex] = queue.shift();
        // 현재 요소가 최대 우선순위를 가지고 있는지 확인합니다.
        if (queue.some(([priority, _]) => priority > currentPriority)) {
            // 만약 더 높은 우선순위의 요소가 있다면, 현재 요소를 큐의 끝에 다시 추가합니다.
            queue.push([currentPriority, currentIndex]);
        } else {
            // 현재 요소를 실행합니다.
            answer++;
            // 현재 요소가 찾고 있는 위치인지 확인합니다.
            if (currentIndex === location) {
                return answer;
            }
        }
    }

    return answer;
}

 

maxPriority값을 따로 구하는것이 아니라, some을 사용해서 queue에서 현재 맨앞(shift)의 우선순위보다 높은게 하나이상이라도 있으면, 탈출할 수 없는 조건문을 만든다. maxPriority는 모든값을 순회해서 최대값을 구해야하지만 some은 true가 되는순간 리턴하기 때문에 좀 더 효율적인 방법이다.

  

function solution(priorities, location) {
    const idxArr=Array(priorities.length).fill(0).map((v,i)=>i);
    const maxPriority=Math.max(...priorities);
    let answer = 0;
    
    while(priorities.length){
        if(priorities[0]<max){ //뒤로가서 다시 줄서기
            priorities.push(priorities.shift());
            idxArr.push(idxArr.shift()); //idx도 똑같이 따라가기
        }else { //탈출
            priorities.shift();
            answer++;
            maxPriority=Math.max(...priorities); //maxPriority 업데이트
            
            if(idxArr.shift()===location){
                return answer;
            }
        }
    }
    
}

예전에 만든

index를 추가한 새로운 array를 만들지 않고, index를 위한 새로운 idxArray를 만드는 방법

똑같은 흐름으로 가야하기 때문에, 우선순위가 뒤로가서 다시 줄서야할때, idxArray값도 똑같이 이동해야한다는 단점이 존재한다.

 

[Lv2] 다리를 지나는 트럭

function solution(bridge_length, weight, truck_weights) {
    let bridge=Array(bridge_length).fill(0);
    let brdigeWeight=0;
    let count = 0;
    
    //1초 증가후, 맨 첫 트럭 진입
    count++;
    bridge.shift(); //?
    brdigeWeight+=truck_weights[0];
    bridge.push(truck_weights.shift());
  
    
    //대기중인 트럭이 있거나, 다리위에 여전히 트럭이 존재할때 (다리에 트럭이 한대이상이라도 존재)
    while(brdigeWeight>0){
        count++; //1초 증가
        brdigeWeight-=bridge.shift(); //큐의 맨앞 꺼내기
        
        //대기중인 트럭중에 다리에 올릴수 있는지 확인
        if(brdigeWeight+truck_weights[0]<=weight && truck_weights.length){
            //다리에 올리기
            brdigeWeight+=truck_weights[0];
            bridge.push(truck_weights.shift());
        }else {
            //무게로 인해 다리에 올릴수 없음
            bridge.push(0);  //흐름을 맞추기위해 0을 삽입
        }
        
    }
    return count;
}

bridge 배열을 통해, 실제 다리를 건너는 과정을 표현하고 시뮬레이션하는데, 트럭이 다리에 진입하면 push하고 다리를 건너면서 전진할때마다 배열에서 한칸씩 앞으로 이동한다. 다리의 끝에 도달하면, 트럭은 배열에서 제거되는 방식이다.

 

✅ shift : 다리위에 트럭이 전진하게 만든다.

✅ push : 다리위에 트럭을 올린다. (truck shift를 통해) , bridgeWeight를 더한다.

 

❗️bridge.length는 항상 동일해야하기때문에, 무게초과로 인해 다음트럭이 다리에 진입하지 못해도 push를 해줘야한다. (0)

첫번째 트럭이 다리에 진입할때는 경우가 다르기때문에 따로 코드를 짜줘야한다. 대기중인 트럭이 있거나, 다리위에 존재하는 경우라면, 다리위에 트럭이 아예 존재하지 않을수 없기때문에 이에 대한 조건문은 weight를 이용한다.

 

 

 

 

[Lv2] 주식가격

function solution(prices) {
    var answer = [];
    
    for(let i=0;i<prices.length;i++){
        let count=0;
        for(let j=i+1;j<prices.length;j++){
            count++;
            if(prices[i]>prices[j]){
                break;
            }
          
            
        }
        answer.push(count);
       
        
    }
    return answer;
}

count를 증가하는 코드를 if문 이후에 써서, 떨어진 가격을 만나게 되면 break로 for문을 빠져나가기 때문에 카운트가 증가되지 못하는 실수가 있었다.