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

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java 

프로그래머스

 

알고리즘은 생각보다 간단하지만 알고리즘 도출하는게 어렵네요

문제 풀이

numbers를 순회하면서 스택에 자기 자신의 인덱스를 넣는데 각 반복마다 현재 순회 중인 값과 스택의 top값을 비교한다.

기본적으로 순회하는 i 값을 스택에 넣을 건데 넣기 전에 스택에 있는 값들이랑 비교하요 자신보다 작은 애들을 찾아낸다.

코드

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

        int[] answer = new int[numbers.length];
        
        // 0번 인덱스부터 시작
        s.push(0);
        for (int i = 1; i < numbers.length; i++) {
            // 현재 numbers[i]보다 작은 스택의 값들을 찾아 answer 지정
            while (!s.isEmpty() && numbers[s.peek()] < numbers[i]) {
                answer[s.pop()] = numbers[i];
            }
            s.push(i);
        }
        
        // 자기보다 큰 값을 못찾아 스택에 남아있는 애들 -1 설정
        while (!s.isEmpty()) {
            answer[s.pop()] = -1;
        }

        return answer;
    }
}