[Algorithm] 뒤에 있는 큰 수 찾기

문제설명

뒤에 있는 큰 수 찾기는 주어진 정수 배열의 정수를 다음 등장하는 더 큰 정수가 있다면 더 큰 정수로 교체하고 없으면 -1로 교체하는 문제이다.

// 2보다 큰 3, 3보다 큰 5, 3보다 큰 5, 5 다음 수가 없으므로 -1
[2, 3, 3, 5] => [3, 5, 5, -1]
// 9보다 큰 수가 없으므로 -1, 1보다 큰 5, 5보다 큰 6, 3보다 큰 6, 6보다 큰 수가 없으므로 -1, 2 다음 수가 없으므로 -1
[9, 1, 5, 3, 6, 2] => [-1, 5, 6, 6, -1, -1]

문제해결

이중반복문으로 해결할 때 효율성 검사 통과가 안된다.

이 경우 stack을 사용하여 중복 탐색을 방지하고 검사하고자 하는 요소만 정확히 확인 할 수 있는 로직이 필요하다.

numbers의 요소를 순회하며 인덱스를 저장한다.

numbers의 최근 인덱스와 현재 인덱스의 요소를 비교할 때 현재 인덱스가 더 크다면 (순회) -1로 초기화된 answer의 값을 현재 인덱스의 요소로 바꿔준다.

function solution(numbers) {
    let answer = new Array(numbers.length).fill(-1),
        stack = [];
    numbers.forEach((num,i) => {
        // 저장된 인덱스가 있을 때
        if (stack) {
            // 최근 숫자보다 현재 숫자가 더 큰 경우 -1을 num으로 교체
            while (numbers[stack[stack.length - 1]] < num) {
                let current = stack.pop();
                answer[current] = num;
            }
        }
        // stack에 최근 인덱스를 저장
        stack.push(i);
    })
    return answer;
}