stack과 친해져라

<뒤에 있는 큰 수 찾기> 문제는... 주어진 배열의 요소들에 대해 자신보다 뒤에 있는 수 중 자신보다 크면서 가장 가까이 있는 수를 찾아 모든 원소에 대한 뒷 큰수를 배열로 반환하는 문제다. 자신보다 큰 수가 없다면 -1을 담는다.

function solution(numbers) {
    return numbers.map((num, i) => numbers.filter((el, j) => el > num && j > i)[0] || -1);
}

사실 냅다 이렇게 filter를 박아버려도 제출 전의 테스트 케이스는 통과를 한다. 하지만..

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

위와 같이 배열의 요소가 1,000,000개 까지 들어올 수 있기 때문에 반복문을 2번 이상 돌리게 되면 시간 초과가 난다!!! 🥲

사실 30분이라는 제한 시간 안에 문제를 풀어내지 못했지만, 다른 사람들의 풀이를 참고하여 다음과 같은 코드를 완성했다.

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

    numbers.forEach((el, i) => {
        while (stack.length && numbers[stack.at(-1)] < el)
            answer[stack.pop()] = el;
        stack.push(i);
    })
    return answer;
}

먼저 반환할 배열을 만들어준 다음 -1로 초기화한다. 그다음 numbers 배열을 forEach() 메소드로 순회하면서, 스택에 담긴 인덱스의 요소(numbers[stack.at(-1)])가 자신(el)보다 작다면 반환할 배열의 해당 인덱스 값에 el을 할당해준다. 그리고 다음 요소의 값과 비교할 수 있도록 자신의 인덱스를 스택에 넣는다.

이전에 <큰 수 만들기> 문제를 풀 때 이런 방법을 사용해서 풀었던 기억이 있다. <큰 수 만들기>는 숫자가 담긴 number 배열의 요소로 만들 수 있는 가장 큰 k자리 숫자를 반환하는 문제다.

function solution(number, k) {
    const arr = [];
    for (let el of number) {
        while (k && arr[arr.length - 1] < el) {
            arr.pop();
            k--;
        }
        arr.push(el);
    }
    return (k ? arr.slice(0, -k) : arr).join('');
}

number 배열을 순회하면서 el보다 스택의 마지막에 위치한 수가 더 작을 때 pop()해주는 방식으로 풀었었다. 저때는 arr를 스택이라고도 생각 못했었는데, 지금 보니 자료구조가 얼핏 보인다! 다음에 이런 방법을 사용하는 문제를 풀 때는 꼭 잘 풀어내야지~~!💪