[JS] 2Level / 연습문제 / 뒤에 있는 큰 수 찾기

문제 설명

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

프로그래머스

 

문제 풀이 방법

• 원래 이 문제를 이중 for문을 이용해 풀어봤다....
  하지만 시간초과가 뜨면서 실패했다.....
  그래서 질문탭에서 스택으로 풀어보라는 글을 보고 스택으로 문제를 풀어봤다.
  그런데도 설계를 잘 못하겠어서 구글링을 통해 다른 분이 작성한 코드를 참고했다.

 

코드 

const solution = (numbers) => {
    let answer = Array.from({length: numbers.length}, () => -1);
    let stack = [];
    
    for(let i=0; i<numbers.length; i++){
        while(stack && numbers[stack.at(-1)] < numbers[i]){
            answer[stack.pop()] = numbers[i];
        }
        stack.push(i);
    }
    return answer;
}

 

let answer = Array.from({length: numbers.length}, () => -1);
let stack = [];

-1로 채워진 배열과 스택으로 이용할 배열을 생성해준다.

 

for(let i=0; i<numbers.length; i++){
    while(stack && numbers[stack.at(-1)] < numbers[i]){
        answer[stack.pop()] = numbers[i];
    }
    stack.push(i);
}

순회중인 현재의 값이 스택에 있는 인덱스에 해당하는 값보다 큰 경우는

FILO인 스택에서 나중에 들어온 인덱스 값 부터 해당하는 answer[stack.pop()] 값에 numbers[i]로 할당해준다.

그리고 while문 이기에 stack && numbers[stack.at(-1)] < numbers[i] 조건에 안맞을 때까지 진행해준다.

 

스택에 아무것도 없거나 있더라도 뒤의 수보다 큰 경우는 stack에 현재 인덱스를 넣어준다.