[프로그래머스/JavaScript] 뒤에 있는 큰 수 찾기(Lv.2)

문제

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

프로그래머스

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

 

---

풀이

• 뒤에서부터 순서대로 Stack에 집어넣는다.
• 집어넣기 전에 Stack에 Empty 상태가 아니라면, peek한 값이 본인보다 큰지 확인.
• 크다면? 뒤에 있는 것 중에 제일 가까우면서 크다 = 뒷 큰 수
• 작다면? pop해버리고 다음 수랑 비교
• JavaScript는 Stack 자료형이 없어서 따로  정의해줬다. (있는 건 아니겠지)

// 프로그래머스 - 뒤에 있는 큰 수 찾기(Lv.2)
class Stack {
  constructor() {
    this.arr = [];
  }

  push(item) {
    this.arr.push(item);
  }

  pop() {
    if (this.arr.length <= 0) return null;
    else return this.arr.pop();
  }
  
  peek() {
    return this.arr[this.arr.length - 1];
  }
  
  isEmpty() {
    if(this.arr.length == 0) return true;
    else return false;
  }
}

const solution = (numbers) => {
  let answer = [];
  const stack = new Stack();

  for(let i = numbers.length - 1; i >= 0; i--){
    while(!stack.isEmpty()){
      // 뒷 숫자 중에 큰 수가 나왔다면 뒷 큰수
      if(stack.peek() > numbers[i]){
        answer[i] = stack.peek();
        break;
      }
      // 뒷 큰수가 아직 안 나왔다면 다음 숫자로 탐색
      // 현재 탐색 중인 수보다 뒤에 있으면서 작은 수이므로 버려도 됨
      // = 앞에 나올 수의 뒷 큰수가 될 수 없음
      stack.pop();
    }

    // stack에 들어있는 수(=현재 수의 뒤에 있는 수) 중에 큰 수가 없을 경우
    if(stack.isEmpty())
      answer[i] = -1;

    // 현재 인덱스 숫자 추가
    stack.push(numbers[i]);
  }

  return answer;
}