[프로그래머스] 뒤에 있는 큰 수 찾기 (Javascript)

코딩테스트 연습 - 뒤에 있는 큰 수 찾기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

알고리즘 : 스택

 

처음에 아무 생각 없이 풀었더니 시간초과...

30분정도 풀어보다가 도저히 모르겠어서 정답을 참고해서 풀었다.

인덱스와 스택을 활용해서 푸는 방식이었는데 아직 시간복잡도를 이해하지 못한 것 같다.

처음에 n이 1,000,000인 것을 보고 n의 시간복잡도로 풀어야겠다! 까지는 되는데 실제 문제를 풀면 어려운것 같다.

 

핵심 알고리즘은 하기와 같다.

1. ans는 -1로 초기화 시켜준다.

2. for문을 돌면서 stack의 마지막 값과 현재의 값을 비교하고, 현재 값이 더 크다면 스택에서 pop해주면서 현재값으로 ans에 추가한다.

3. while문에 걸리지 않으면 stack에 그대로 넣어준다. 

 

function solution(numbers) {
    
   let ans = new Array(numbers.length).fill(-1);
  let stack = [];

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




    return ans;
}