[프로그래머스 / Java] Lv.2 뒤에 있는 큰 수 찾기

Question

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

프로그래머스

---

Algorithm

1. 이전에 본 값들의 인덱스를 저장해두고, 더 큰 수가 나올 때까지 비교해야 하므로 스택을 사용한다.
2. 배열을 왼쪽부터 오른쪽으로 순회하면서, 현재 숫자가 스택 top 인덱스의 값보다 크면 answer 값을 갱신한다.
3. 아직 이 인덱스의 값보다 큰 수를 못 찾았은 경우, 뒤에서 더 큰 수를 만날 때까지 대기시키기 위해 스택에 보관한다.
4. 배열 순회가 끝난 후, 스택에 남아 있는 인덱스들은 더 큰 수를 못 만난 것이므로 answer를 -1로 채운다.

---

Code

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] solution(int[] numbers) {
        
        int[] answer = new int[numbers.length];

        // 인덱스를 저장할 스택 (Deque 사용, LIFO 구조)
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 배열을 순회하면서
        for (int i = 0; i < numbers.length; i++) {
            // 현재 숫자가 스택의 top에 해당하는 인덱스의 값보다 크다면
            // 해당 인덱스에 대한 "뒤에 있는 큰 수"를 찾은 것
            while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                // 스택에서 인덱스를 꺼내고
                int index = stack.pop();
                // 해당 위치에 현재 숫자를 저장
                answer[index] = numbers[i];
            }
            // 현재 인덱스를 스택에 추가 (아직 뒤에 있는 큰 수를 못 찾은 상태)
            stack.push(i);
        }

        // 스택에 남아있는 인덱스들은 "뒤에 있는 큰 수"가 없었던 것
        while (!stack.isEmpty()) {
            int index = stack.pop();
            answer[index] = -1; // 뒤에 더 큰 수가 없으므로 -1 설정
        }

        return answer; // 결과 배열 반환
    }
}

---

출처

https://hb-in99.tistory.com/59

프로그래머스 - 뒤에 있는 큰 수 찾기 <9점> - 자바 java Stack