[JS] 프로그래머스 - 뒤에 있는 큰 수 찾기

📌  문제

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다. 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

💡  아이디어

이중 for문 돌면서 자기보다 큰 수 발견하면 answer에 push하고 break -> 테케 4개 시간초과
이중 for문을 한번으로 줄여야 할 것 같은데..
스택을 이용해서 해야되는 건 알겠는데 어떻게 해야할지 몰라서 검색해봤는데도 이해가 안됬다ㅠㅠ..
그림까지 사용해서 친절하게 설명해둔 블로그가 있어서 이해 할 수 있었다 🥹

출처 : https://sasca37.tistory.com/306#google_vignette

✏️  풀이

// 시간초과 코드

function solution(numbers) {
  var answer = [];
  for(let i=0; i<numbers.length; i++){
    let include = false;
    for(let j=i; j<numbers.length; j++) {
      if(numbers[i] < numbers[j]) {
        answer.push(numbers[j]);
        include = true;
        break;
      }
    }
    if(!include) answer.push(-1);
  }
  return answer;
}

 

function solution(numbers) {
  var answer = new Array(numbers.length).fill(-1);
  const stk = [];
  // 인덱스가 담길 스택
  
  for(let i=0; i<numbers.length; i++) {
  // numbers 배열을 돌면서
      while(stk && numbers[i] > numbers[stk[stk.length-1]]) {
      // 스택이 비어있지 않고, 현재 스택에서 제일 위의 값(인덱스)을 꺼내오고 그 인덱스의 값보다 비교 대상이 크다면
      // 비교 대상이 되는 값이 제일 가까운 큰 값!
          answer[stk.pop()] = numbers[i];
          // 스택에서 제일 위의 값(인덱스)을 pop해서 answer의 인덱스에 제일 가까운 큰 값을 넣어준다.
      }
      stk.push(i);
      // 스택에는 항상 인덱스가 저장됨!!
  }
  return answer;
}