프로그래머스 뒤에 있는 큰 수 찾기

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154539

문제 풀이

기존의 2중 for문을 통해 검사를 할 경우 최대 100만 x 100만의 시간 복잡도로 시간초과 오류가 발생

따라서 100만 x ?? 부분을 효율적으로 처리를 해야함

---

stack을 이용한 풀이

1. numbers를 순차적으로 진행

2. stack에 값이 있고, stack의 마지막 값에 해당하는 numbers값이 현재(i번째) numbers값 보다 작은 경우 stack 마지막 값을 i번째 값으로 설정

3. 이후 i를 stack에 추가

---

[9, 1, 5, 3, 6, 2]를 예시로 들면

9 -> 1 인 경우 stack은 [0, 1]이 쌓여있음 이후 5에 대해 검사를 하게 되면 위 2번 로직을 통해 1번째 index 값이 5로 저장이 됨

즉, 현재 기준 값(i)으로 stack의 값들을 처리해 나가면 됨

function solution(numbers) {
    const answer = new Array(numbers.length).fill(-1);
    const stack = [];
    
    for (let i = 0; i < numbers.length; i++) {
        while (stack.length > 0 && numbers[stack[stack.length - 1]] < numbers[i]) {
            const index = stack.pop();
            answer[index] = numbers[i];
        }
        stack.push(i);
    }
    
    return answer;
}

---

결론

stack자료구조를 활용해서 문제를 접근하면 됨

위에서 언급된 2번 로직을 생각하는게 이 문제의 핵심인 것 같음