[프로그래머스/자바스크립트] 스택/큐 문제 풀이 모음

1. 같은 숫자는 싫어 - lv1

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

프로그래머스

연속으로 나타나는 수는 하나만 남기고 나머지는 제거하는 문제이다. 배열보다 filter를 사용하면 간단하게 풀 수 있다.

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

값이 다음 값과 같은 경우에는 걸러낸다.

배열을 사용하면 이렇게 풀 수 있다.

function solution(arr)
{
    var answer = [arr[0]];
    
    arr.forEach(v => answer[answer.length-1] !== v ? answer.push(v) : '');
    
    return answer;
}

우선 arr의 첫번째 값을 배열에 넣는다.

그 다음 arr를 forEach로 순회하면서 값이 answer.peek()값과 다른 경우에만 배열에 값을 push한다.

 

2. 기능개발 - lv.2

https://school.programmers.co.kr/learn/courses/30/lessons/42586?language=javascript

프로그래머스

작업 진도를 x, 작업 속도를 y라 하고 배포 가능 상태가 되기까지 걸리는 날은 다음과 같이 구할 수 있다.

Math.ceil((100 - x) % y)

 

위 공식으로 구한 [93, 30, 55]가 배포 가능 상태가 되기까지 걸리는 날은 [7, 3, 9]다. (이하 prog)

두 번째 값 3은 첫 번째 값 7이 먼저 배포될 때까지 기다렸다가 7과 함께 배포된다. 그리도 이틀 뒤에 9가 배포된다. 즉 반환값은 [2, 1]이 된다.

이를 다음과 같이 정리했다.

• 배포날인 n을 prog의 첫 번째 값으로 초기화(배포)하고 배열에서 그 값을 삭제한다.
• 반환값 answer 배열은 [1]로 초기화한다. 7 하나가 배포되었기 때문이다.
• 이제 prog 배열을 순회하면서 값 x가 n보다 작거나 같을 때는 함께 배포한다. (answer[answer.length-1]++)
• n보다 큰 경우에는 배포날이 다르므로 answer에 1을 push하고 n을 x로 바꾼다.

function solution(progresses, speeds) {
    progresses = progresses.map((x, i) => Math.ceil((100-x)/speeds[i]));
    
    var answer = [1];
    var n = progresses.shift();
    
    progresses.forEach((x, i) => {
        if(x <= n) answer[answer.length - 1]++;
        else { answer.push(1); n = x; }
    })
    
    return answer;
}

 

3. 올바른 괄호 - lv.2

처음에는 replaceAll()을 사용해서 풀었지만 효율성에서 시간초과가 떴다. replaceAll()이 문자열 전체를 탐색하기 때문에 시간 복잡도가 높기 때문이다.

function solution(s) {
    while (s.length > 0) {
        var copy = s;
        s = s.replaceAll('()', '');
        if (s === copy)
            return false;
    }
    return true;
}

정석대로 스택을 사용해서 풀면 한번만 순회하여 시간초과가 뜨지 않는다.

1. 주어진 문자열을 순회한다.
2. 문자가 '('이면 배열에 push한다.
3. ')'인 경우
   1. 배열이 비어있으면 올바른 괄호가 아니기 때문에 false를 반환한다.
   2. 비어있지 않으면 배열을 pop한다.(배열에는 '('만 들어있기 때문)
4. 순회가 끝나고 배열이 비어있으면 true를, 아니면 false를 반환한다.

function solution(s) {
    var arr = [];
    for (let c of s) {
        if (c === '(') arr.push(c);
        else {
            if (arr.length === 0) return false;
            else arr.pop();
        }
    }
    return arr.length === 0;
}