[Programmers] 뒤에 있는 큰 수 찾기

스택 자료구조 특성상 FIFO을 이용한 풀이이다.

 

1) 스택에 인덱스 값을 저장

 

2) 하강하는 배열이면 바로 스택에 추가하여 관리한다.

 

3) 스택의 가장 peek 값인 제일 최신의 앞 자리수와 현재 들어온 뒷 자리인 값을 비교

 

4) 뒷 자리가 스택의 peek 부분 보다 크다면 바로 뒤에 존재하는 큰 수 이다. 이 때의 값을 answer 배열에 저장하고 이때 사용된 numbers 값은 스택에 집어 넣어서 다음에 나올 뒷 숫자와 비교를 진행한다.

 

※ 스택에 들어가는 수들은 다음 숫자와의 비교를 위해서 들어가고 스택은 FIFO 인 것을 생각해야 보인다.

import java.util.*;
class Solution {
    public static int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer, -1);
        Stack<Integer> st = new Stack<>();
        for(int i = 0; i < numbers.length; i++) {
        	if(st.isEmpty() || numbers[i] < numbers[i-1]) {
        		st.add(i);
        	}else {
        		while(!st.isEmpty() && numbers[st.peek()] < numbers[i]) {
        			answer[st.pop()] = numbers[i];
        		}
        		st.add(i);
        	}
        }
        return answer;
    }
}