프로그래머스 lv2 뒷 큰수 구하기

문제 요구사항

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

접근방법 (시간초과)

function solution(numbers) {
  var answer = [];

  let max = Math.max(...numbers); // 9

  for (let i = 0; i < numbers.length; i++) {
    for (let j = i; j < numbers.length; j++) {
      if (numbers[i] === max) {
        answer.push(-1);
        break;
      }

      if (numbers[i] < numbers[j]) {
        answer.push(numbers[j]);
        break;
      }

      if (j === numbers.length - 1) {
        answer.push(-1);
        break;
      }
    }
  }
  return answer;
}

우선 위에 코드는 이중 반복문을 순회하기 때문에 시간초과 오류가 난 것 같다. 문제에서 요구하는 사항은 for문 하나로 해결해야 하는데 시간복잡도를 생각하지 못하고 구현하는데 급급해서 틀린것 같다. 하지만 개인적으로 코드가 직관적이기도 맘에 드는 풀이였다.

해답

function solution(numbers) {
  const answer = Array(numbers.length).fill(-1);
  const stack = [];

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

30분 정도 고민을 했는데 답이 나오지 않아서 다른 분들의 풀이를 참고했다. 스택을 이용하면 for문 하나에 해결할 수 있었다. 우선 이 방법은 전혀 생각지 못한 방법이기도 했다.

우선 Array.prototype.at 함수부터 알아야 한다.

//Array.prototype.at 메서드 -> 매개변수로 인덱스 번호 -> 해당하는 // 인덱스의 값을 리턴함 음수 매개변수로 뒤에서부터 접근할 때 유용함

 const array = [1, 2, 3, 4, 5];
 console.log(array.at(0)); // 1
 console.log(array.at(3)); // 4
 console.log(array.at(-1)); // 5
 console.log(array.at(-2)); // 4

이 문제의 해결법은 자신보다 크면서 가장 가까이에 있는 수를 비교하는 것이다.

예를 들어 매개변수가 [9, 1, 5, 3, 6, 2] 이렇게 주어진다고 가정해보자

처음에 스택에 0이 push 되고
i 가 1이된다.
그 다음 numbers[0] 과 numbers[1]을 비교한다. 9 < 1 은 false 임으로
스택에 1이 푸쉬된다. -> 현재 스택 [0,1]
i 가 2가된다.
numbers[1] 과 numbers[2]를 비교한다. 1 < 5 는 true 임으로
answer[1] 은 numbers[2] 즉 5가된다.
스택에 남은
그 다음 numbers[0] 과 numbres[2] 를 비교하고 false 임으로
스택에 2 를 푸쉬함 -> 현재 스택 [0,2]
...

이런식으로 스택에는 아직 비교되지 않은 원소의 인덱스를 푸쉬하고
조건을 만족하는 (가까이에 있는 가장 큰수) 이면 그 수를 푸쉬한다.

스택 과 큐 라는 자료구조는 알고 있었지만 막상 문제에 적용하려고 하니 좀 힘들었다. 다음에 다시 한 번 더 풀어볼만한 문제이다.