Programmers / Level 2 / 뒤에 있는 큰 수 찾기 / JS

문제 간단설명

정수로 이루어진 배열 numbers가 있다.

각 수에 대해서 가장 가깝고 자신보다 큰 수를 '뒷 수'라고 한다.

각 요소에 대해 '뒷 수'들을 모아서 배열로 반환하면 된다.

만약 뒷 수가 존재하지 않는다면 -1을 반환하면 된다.

 

제한 사항

• 4 <= numbers의 길이 <= 1,000,000
  • 1 <= numbers[i] <= 1,000,000

 

실패 코드 (시간 초과)

function solution(numbers) {
    const result = [];
    
    for(let i=0; i<numbers.length; i++) {
        const cur = numbers[i];
        
        let backNumber = -1
        for(let j=i+1; j<numbers.length; j++) {
            const next = numbers[j];
            
            if(next > cur) {
                backNumber = next;
                break;
            }
        }
        
        result.push(backNumber);    
    }
    
    return result;
}

 

최악의 경우에 O(n^2)의 시간복잡도를 가지는 코드이다.

만약 1,000,000개의 수가 1,000,000부터 1까지 내림차순으로 되어있다면, 모든 수에 대해서 배열의 끝까지 순회할 것이다.

그러므로 1,000,000^2 = 1조에 해당한다. 약 1억건의 연산이 1초가 걸린다고 통용되므로, 약 1만초쯤 걸린다고 생각하면 된다.

 

성공 코드

function solution(numbers) {
  const result = Array.from({ length: numbers.length }, () => -1);
  const stack = [];

  for (let i = numbers.length - 1; i >= 0; i--) {
    const cur = numbers[i];
    // stack이 비어있지 않고, stack의 top이 현재 요소 이하일 경우
    while (stack.length > 0 && stack.at(-1) <= cur) {
      // 현재값보다 큰 수가 아니므로 stack에서 제거한다.
      stack.pop();
    }

    // stack이 비어있지 않을 경우
    if (stack.length > 0) {
      // 현재 위치의 요소보다 큰 값은 stack의 top에 있다.
      result[i] = stack.at(-1);
    }

    // stack의 top에 현재 요소를 넣는다.
    stack.push(cur);
  }

  return result;
}

 

stack 자료구조를 사용했다. 여기서 stack에 저장하는 수는, 주어진 numbers를 거꾸로 순회하면서, 현재 값보다 뒤에 있는 수들이다.

 

예를 들어, [2, 3, 3, 5]가 있는 배열이 있다고 하자. 이 배열을 거꾸로 순회하면서 stack에 저장하게 되면, 현재 인덱스에 해당하는 값이 2일때 stack에는 [3, 3, 5]가 들어있게 된다.

 

하지만 모든 값을 계속 저장해두는 것은 아니다. 문제에서 구해야 하는 값은 현재 값보다 크면서 뒤에 있는 가장 가까운 수를 구하는 것이기 때문에, 현재 값 이하의 값은 stack에서 pop한다.

 

그리고 나서, 결과 배열에 현재 순회중인 인덱스의 위치에 stack의 top을 넣어준다. stack의 top은 현재 순회중인 값중에 가장 가까운 큰 수 이기 때문이다.

 

그 후, 다음 반복을 위해 현재 값을 push 해준다.

 

한번만 순회하기 때문에 O(n)의 시간복잡도를 가지므로, 시간초과 없이 통과할 수 있다.