[프로그래머스 알고리즘 고득점 Kit] 문제풀이 - 스택 / 큐

1. 같은 숫자는 싫어

https://school.programmers.co.kr/learn/courses/30/lessons/12906

프로그래머스

1-1. 내 풀이

이미 푼 문제인데 나는 filter 를 사용하여, 앞에 있는 숫자와 같을 경우 해당 숫자를 필터링하여 연속으로 중복된 수를 제거하였다.

function solution(arr) {
    return arr.filter((item,idx) => item !==arr[idx-1]);
}

1-2. 다른 사람 풀이

나와 같은 방식으로 해결하였다.

function solution(arr) {
    return arr.filter((val,index) => val != arr[index+1]);
}

 

2. 기능개발

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

2-1. 내 풀이

반복문이 너무 많지만 이렇게 풀었다. progresses 가 0이 될 때까지 반복문을 돌렸고, progresses 의 첫 번째가 100 이 될 때까지 반복문을 사용해 개발작업을 하는 로직을 구현하였다. 그리고 progresses 에서 첫 번째 요소부터 100이 넘는 건 숫자로 세고 배열에서 제거하였으며 100보다 작으면 배포를 할 수 없어 break 문을 적용시켰다. 그리고 배포된 수를 arr 에 넣었다.

function solution(progresses, speeds) {
    let arr = [];
    
    for(j=0; progresses.length !== 0; j++) {
         while (progresses[0] < 100) {
            for(i=0; i<progresses.length; i++) {
                progresses[i] += speeds[i]
            }
        }
        
        let cnt = 0;
        
        for(k=0; progresses.length !== 0; k++) {
            if(progresses[k]>=100) {
                cnt++;
                progresses.splice(k, 1);
                speeds.splice(k, 1);
                k--;
            } else break;
        }
        
        arr.push(cnt);
    }
    return arr;
}

2-2. 다른 사람 풀이

나는 첫번째 요소가 배포되기 위해 바로 100으로 만들고 배포를 시작했는데 이 사람은 하루치를 구현하는 작업을 하였다. 그래서 100보다 큰 날이 있으면 그때 배포 작업 구현을 하였고 나처럼 splice 를 사용하는 대신 shift 를 사용하여 맨 앞에 있는 요소를 삭제하였다.

function solution(progresses, speeds) {
    var answer = [];

    while(speeds.length > 0) {
        // 개발
        for(let i in speeds) {
            if(progresses[i] < 100) {
                progresses[i] += speeds[i];
            }
        }

        // 배포
        let deploy_count = 0;
        while(progresses[0] >= 100) {
            progresses.shift();
            speeds.shift();
            deploy_count++;
        }
        if(deploy_count > 0) {
            answer.push(deploy_count);
        }
    }

    return answer;
}

 

3. 올바른 괄호

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

3-1. 내 풀이

처음에 2, 6번 케이스를 실패했었다. 반례를 보니 비어진 상태에서 pop 을 하면 그대로 비어진 상태라서 true 가 리턴되게 된다. 그래서 pop 을 할 때, result 가 비어져있지 않을 때만 pop 을 하고, 비어 있으면 push 를 하였다.

function solution(s){
    const arr = s.split('');
    const result = [];
    
    arr.map((item)=>{
        if (item === '(') result.push('(');
        else {
            if (result.length === 0) result.push(')');
            else result.pop();
        }
    })
    
    return result.length === 0;
}

3-2. 다른 사람 풀이

( 이면 1을 더하고 ) 이면 1을 빼서 결과가 0이면 true 를 반환했다. 스택말고 더 간단하게 풀 수 있는 거 같다.

function solution(s){
    let cum = 0
    for (let paren of s) {
        cum += paren === '('? 1: -1
        if(cum < 0) {
            return false
        }
    }
    return cum === 0? true: false;
}

 

4. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

4-1. 내 풀이

몇십분을 고민해도 문제를 풀지 못해 다른 사람들이 푼 것을 참고하여 다음날 풀었다. priorities 값이랑 index 가 배열로 된 twoArr 를 만들고  priorities 맨 앞에 있는 수가 가장 큰 수보다 작으면 뒤에 추가하고, 같으면 그 수를 빼고 result 배열에 넣었다. 그리고 만약 twoArr 의 index 와 location 값이 같으면 result 의 길이를 반환했다.

function solution(priorities, location) {
    const result = [];
    const twoArr = priorities.map((item,idx)=>{
        return [item,idx]
    })
    
    while(priorities.length) {
        const big = Math.max(...priorities);
        
        if (priorities[0] < big) {
            priorities.push(priorities.shift());
            twoArr.push(twoArr.shift());
        } else {
            result.push(priorities.shift());
            if (twoArr.shift()[1] === location) return result.length
        }
    }
}

4-2. 다른 사람 풀이

list 라는 배열에 객체를 넣어 index 가 location 과 같으면 true 로 되어있다. 그리고 while 문을 통해 첫 번째 값을 cur 에 두고, cur 보다 큰 수가 있으면 다시 배열 뒤에 넣었고, 만약 큰 수가 없다면 count 값을 반환했다.

function solution(priorities, location) {
    var list = priorities.map((t,i)=>({
        my : i === location,
        val : t
    }));
    var count = 0;        
    while(true){
        var cur = list.splice(0,1)[0];        
        if(list.some(t=> t.val > cur.val )){
            list.push(cur);                        
        }
        else{            
            count++;
            if(cur.my) return count;
        }
    }
}

 

5. 다리를 지나는 트럭

https://school.programmers.co.kr/learn/courses/30/lessons/42583

프로그래머스

5-1. 내 풀이

이 문제도 몇십분을 고민해도 문제를 풀지 못해 다른 사람들이 푼 것을 참고하여 다음날 풀었다. 다리의 길이만큼 0으로 채운 배열 load 를 만들었고, load 의 합과 새로 들어올 트럭의 합이 weight 보다 작거나 같으면 load 에 트럭을 넣어주고, 그렇지 않으면 load 에 0 을 넣었고 시간을 증가시켰다. 그리고 차가 다 load 에 들어가면 while 문이 끝나고 마지막차가 다 건널 때까지 시간을 더해줘 값을 구했다.

function solution(bridge_length, weight, truck_weights) {
    let time = 0;
    let load = Array(bridge_length).fill(0);
    
    while(truck_weights.length) {
  
        load.shift();
        
        const sum = load.reduce((a,b) => a + b, 0);
     
        if(sum + truck_weights[0] <= weight) {
            load.push(truck_weights.shift());
        } else {
            load.push(0);
        }
        
        time++;
    }
    
    return time + bridge_length;
}

 

6. 주식가격

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

6-1. 내 풀이

주식 가격이 떨어지면 break 를 하여 for 문을 나온 후, i 에서 j 를 뺀 값의 절댓값을 사용하여 유지 시간을 배열에 넣었다. 그리고 마지막은 뒤에 결과를 알 수 없어 유지시간이 항상 0 이라 마지막에 0 을 배열에 넣어 구했다.

function solution(prices) {
    const arr = [];
    
    for(i=0; i<prices.length-1; i++) {
        for(j=i+1; j<prices.length-1; j++) {
            if (prices[i] > prices[j]) {
                break;
            }
        }
        arr.push(Math.abs(i-j));
    }
    
    arr.push(0)
    
    return arr;
}