이 문제는 계속 시간 초과가 나서 chatGPT의 도움을 받아봤다.

문제

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

제한사항

4 ≤ numbers의 길이 ≤ 1,000,000
1 ≤ numbers[i] ≤ 1,000,000

입출력 예

numbers         	result
[2, 3, 3, 5]    	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

입출력 예 설명

입출력 예 #1
2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2
9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

chatGPT의 도움을 받은 코드(3점)

function solution(numbers) {
// index를 저장할 stack 배열 선언
  const stackIndex = [];
  // 앞으로 이 result 배열의 원소를 각각 뒤 큰 수로 바꿀 것이다.
  const result = new Array(numbers.length).fill(-1);
  
  for (let i = 0; i < numbers.length; i++) {
    while (stackIndex.length > 0 && numbers[stackIndex[stackIndex.length-1]] < numbers[i]) {
    // 뒤 큰 수를 찾아 헤매고 있던 주인공의 index
      const top = stackIndex.pop();
      // 주인공은 바로 현재 i번째 numbers
      result[top] = numbers[i];
    }
    stackIndex.push(i);
  }
  
  return result;

입력값이 [2, 3, 3, 5]일 때 for문에서 i = 0부터 i = 3까지 코드가 어떻게 동작하는지 차근차근 살펴보자.

i = 0일 때

while문 조건에서 일단 stackIndex가 빈 배열이어서 길이가 0이므로 while문에 진입하지 않는다. 대신 stackIndex에 0을 push 한다.

stackIndex = [ 0 ];
result = [-1, -1, -1, -1];

i = 1일 때

while문 조건에서 stackIndex의 길이가 1이 되어 0보다 커졌고, stackIndex의 마지막 원소는 0, numbers[0] === 2이고 numbers[1] === 3인데 후자가 더 크므로 while문에 진입한다.
이 때 top = 0이 되고, result[0] = 3 (=== i번째 숫자)이 된다.

그리고 더 이상 stackIndex에 원소가 없으므로 길이가 0이 되어 while문을 빠져나온다.

stackIndex = [ 1 ];
result = [3, -1, -1, -1];

i = 2일 때

while문 조건에서 stackIndex의 길이가 1이 되어 0보다 크고, stackIndex의 마지막 원소는 1, numbers[1] === 3이고 numbers[2] === 3인데 전자와 후자가 같으므로 while문에 진입하지 않는다. stackIndex에 2만 push 한다.

stackIndex = [ 1, 2 ];
result = [3, -1, -1, -1];

i = 3일 때

while문 조건에서 stackIndex의 길이가 2로 0보다 크고,
stackIndex의 마지막 원소는 2, numbers[2] === 3이고 numbers[3] === 5인데 후자가 더 크므로 while문에 진입한다.
이 때 top = 2가 되고, result[2] = 5 (=== i번째 숫자)가 된다.

여전히 while문은 끝나지 않는다.
stackIndex의 길이가 아직 1이어서 0보다 크고,
stackIndex의 마지막 원소는 1, numbers[1] === 3이고 numbers[3] === 5인데 후자가 더 크므로 while문에 다시 진입해야 한다.
이 때 top은 1이고, result[1] = 5 (=== i번째 숫자)가 된다.

이 코드는 처음에 이해하기 아주 어려웠다. 내가 자주 쓰던 stack 패턴을 사용했더니 시간 초과가 났었고, 그 코드랑 패턴이 많이 달랐다. 그래도 차근차근 노트에 동작 원리를 써보니까 이해는 된다. 비슷한 문제가 백준에 나온다면 또 풀어보고 싶다!

최근에 며칠동안 아팠더니 미뤄놨던 리뷰할 코드가 산더미 같다 ㅠㅠ 하나씩 차근차근 뜯어보자 화이팅!!!