[JS] 뒤에 있는 큰 수 찾기

 

 

난이도: Lv. 2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

 

알고리즘

1. 정답 배열의 모든 원소를 -1로 초기화한다.

2. 스택에 [numbers의 원소, 원소의 인덱스] 배열을 넣는다.

3. 2.를 수행하기 전에 스택 안에 있는 원소들이 새로 넣을 원소보다 작으면 스택을 pop() 하여 꺼낸 원소의 원래 인덱스를 확인하고 정답 배열의 해당 인덱스를 새로 넣을 원소의 값으로 바꾼다. 새로 넣을 원소가 스택에 있는 원소보다 클 경우 3. 의 과정을 반복한다.

 

 

코드

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

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

    return answer;
}

 

 

주저리

처음에 뒤에 있는 원소들 중에서 가장 큰 수 고르는 문제인 줄 알고 쉬운데 왜 정답률이 낮지 했는데 그런 문제가 아니었다. 잘못됨을 깨닫고 O(n^2)으로 풀었는데 아니나 다를까 시간초과가 났다. 근데 무슨 자료구조를 써야 하는지 모르겠어서 질문하기를 보니까 스택으로 푸는 거라고 해서 그거 알고는 금방 풀었다. 자신보다 크면서 가장 가까이 있는 수라고 했기 때문에 스택으로 푸는 문제라고 한다. 어떻게 그 문장만 보고 스택으로 풀어야 한다는 걸 깨달은 건지 신기하고 나는 바보다.