[프로그래머스] 뒤에 있는 큰 수 찾기 - Java

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

프로그래머스

프로그래머스 뒤에 있는 큰 수 찾기 자바 풀이

난이도: Lv2

 

풀이

뒤에 부터 검사하여 더 큰수가 있는지 비교한다.

int[] numbers={2, 3, 6, 8, 5, 6, 4, 7} 라고 가정했을 때

 

7보다 더 큰 수가 없으므로 -1, 그 후 7을 스택에 넣음

4와 6을 비교했을 때 7이 더 크므로 7, 4를 스택에 넣음

6과 4를 비교했을 때 4가 작아, 4를 스택에서 제거 

6과 7을비교했을 때 7이 더 크므로 7, 6을 스택에 넣음

이런식으로 진행한다.

 

가장 가까운 수 중 뒤에 있는 큰 수를 찾는 것이기 때문에,

Stack에서 꺼낸 수와 비교했을 때 꺼낸 수가 더 작은 경우 제거하여도 상관없다.

숫자를 비교하였을 때 가까운 수인 경우를 비교하며, 더 작은 수인 경우 비교할 때 이미 더 작기 때문에 비교할 필요가 없다.

 

코드

import java.util.Stack;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();

        for(int i=numbers.length-1;i>=0;i--){
            while (!stack.empty()&&numbers[i]>=stack.peek()) {
                stack.pop();
            }

            if(!stack.empty()){
                answer[i]=stack.peek();
            }else{
                answer[i]=-1;
            }

            stack.push(numbers[i]);
        }
        return answer;
    }
}