Lv.2 뒤에 있는 큰 수 찾기 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(17분 38초)

아이디어

이 문제는 백준에 있는 오큰수와 동일한 문제이다. 푼지 3년이 넘었기에 기억이 안나서 처음에 생각만 10분정도 했다.

떠오른 아이디어는 어차피 현재 위치의 수가 오른쪽에 존재하는 수보다 클 때 그 수가 현재 위치의 수의 왼쪽 수보다 커서 적힐 정답 배열에 적힐 일은 없다. 말이 좀 어려운데 동작으로 설명하면 뒤에서부터 지나오면서 스택에다 넣어주는데
그렇게 하다가 자기보다 큰 수를 찾을때까지 stack을 pop시킬 때 pop당한 수들은 어차피 현재 비교 기준인 수보다 작은 수들이기에
고려할 필요가 없다는 말이다.

numbers result
[2, 3, 3, 5] [3, 5, 5, -1]
예제 1번으로 설명하면

1. 만약 5라면 스택이 비어있기에 -1을 배열에 넣고 스택에 5추가
2. 3이 나오면 스택의 peek인 5가 3보다 크기에 배열에 5을 넣고 스택에 3을 추가
3. 3이 나왔으면 peek이랑 작거나같기에 큰 peek이 나올때까지 pop해주고 5가 나오면 배열에 넣고 스택에 3을 추가

이런식으로 반복을 해준다.
자신보다 peek이 같거나 작을 경우엔 자기보다 큰 peek이 나올때까지 뽑아야하는데
이때 stack이 비었을때 뽑는거 조심, 그리고 빌때까지 안나오면 -1넣기
그렇게 끝까지 진행해주고 answer배열 return해주면 끝.

풀이 코드

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for(int i=numbers.length-1; i>=0; i--){
            //stack이 비어있을 경우
            if(stack.isEmpty()){
                answer[i] = -1;
                stack.addLast(numbers[i]);
            }
            //stack.peek이 number보다 큰 경우
            else if(stack.peekLast() > numbers[i]){
                answer[i] = stack.peekLast();
                stack.addLast(numbers[i]);
            }
            //stack.peek이 number보다 작은 경우
            else{
                while(!stack.isEmpty()&&stack.peekLast()<=numbers[i]){
                    stack.pollLast();
                }
                //stack이 비어버린 경우 -1넣기
                if(stack.isEmpty()){
                    answer[i] = -1;
                }
                else {
                    answer[i] = stack.peekLast();
                }
                stack.addLast(numbers[i]);
            }
        }
        return answer;
    }
}