아찌방 하우스

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

풀이 - 나의 생각

뒤에 있는 나보다 큰 수를 찾는 것이기 때문에

뒤에서부터 찾으면 수월할 거라고 생각을 했다.

최악의 경우

1, 1, 1 , 1 , 1 , 1 , 1 , 1 --------------------------, 9

이런 경우

단순히 반복문으로 i = 0,1,2,3 --- n-1 의 경우

i = n 까지 뒤져 봐야 하는데

너무 비효율적이라고 생각했기 때문이다.

결국 문제는 나보다 큰 수가 어디 있을지 모르는 것이다.

그래서 뒤에서부터 찾기로 했다.

Stack을 사용(여기서는 Deque를 사용했지만)해서

값들을 저장하는데

나보다 큰 값을 찾을 때까지 Stack에 있는 값들을 다 빼낸다.

나보다 큰 값이 있으면 answer에 저장하고 끝낸다.

그리고 나보다 큰 값을 못찾으면 -1을 저장한다.

[9, 1, 5, 3, 6, 2]이 주어졌을 때

이런식으로 진행 된다.

현재 값을 Stack에 계속 넣는 이유는

바로 뒤의 값이 큰 경우를 대비한다고 생각하면 된다.

코드

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Deque<Integer> bigNums = new ArrayDeque<>();
        bigNums.offer(numbers[numbers.length-1]);
        
        answer[answer.length-1] = -1;
        for(int i = numbers.length - 2; i >= 0; i--){
            int front = numbers[i];
            
            while(!bigNums.isEmpty()){
                if(front < bigNums.peek()){
                    answer[i] = bigNums.peek();
                    break;
                }else{
                    bigNums.poll();
                }
            }
            if(bigNums.isEmpty()){
                answer[i] = -1;
            }
            bigNums.offerFirst(front);
        }
        return answer;
    }
}