baekjoon. 탑

문제

링크

풀이

스택을 이용해서 풀 수 있는 문제

주어진 배열에서 수(A)를 하나씩 꺼내고 스택 가장 위에 있는 수(B)와 크기 비교를 해서 A가 B보다 크다면 A보다 큰 수가 나올 때 까지 스택을 뺀다

그렇지 않다면 A를 스택에 넣는다

스택을 이용하는 아주 쉬운 문제인데 한 가지 문제는 몇 번째 숫자와 비교했는지 알아내서 스택에서 수를 언제 빼냈는지 기억해야 한다는 것

배열에서 수 A를 빼 내올 때 value와 index를 동시에 빼와서 인덱스를 이용해주면된다

코드

    function solution(input){
        const tops = input.split('\n').slice(1)[0].split(' ').map((v,i)=>[Number(v),i]);
        const stack = [];
        const answer = Array(tops.length).fill(0);

        Array.prototype.peek = function (){
            return (this[this.length-1]||[])[0] || false;
        }

        while (tops.length){
            const [temp,index] = tops.pop() ;

            if(!stack.length){
                stack.push([temp,index]);
                continue;
            }
            if(stack.peek()<=temp){
                while (stack.peek()<=temp&& stack.length){
                    const [_,idx] = stack.pop();
                    answer[idx] = tops.length+1;
                }
                stack.push([temp,index]);
                continue;
            }
            stack.push([temp,index]);
        }
        console.log(answer.join(' '));
    }

Array.prototype.peek

내가 구현한 알고리즘의 특성상 배열과 스택의 가장 마지막 데이터를 계속 비교해주어야하는데

stack[stack.length-1]을 계속 쓰기 힘들기도하고 가독성도 너무 떨어져서

다른 언어에서 배열의 가장 마지막에 집어넣은 데이터를 보여주는 peek을 직접 구현했다

temp, index 두개가 들어가있는 2차원 배열이기 때문에 [0]을 붙여줬고 배열의 크기가 0일 때 에러가 나지않게 하기위해 예외처리도 해주었다