[Programmers] 뒤에 있는 큰 수 찾기 - Java

문제

프로그래머스

 

풀이

스택에 인덱스를 저장하는 것을 이용한다.

데이터의 수가 100만개이기때문에, O(NlogN)연산으로 끝내야한다.

일단 데이터의 수가 4개 이상이 되기 때문에, 0번 인덱스를 넣는다.

i번 인덱스 값과 이전 스택들의 값을 비교해서, 스택에서 제일 위에 있는 데이터보다 더 작다면, 뒤 큰수라고 생각하고 다 기록해버린다.

뒤 큰수를 넣고, 다음 인덱스를 돌면서 뒤 큰수를 기록한다.

 

소스코드

import java.util.ArrayDeque;

class Solution {
    public int[] solution(int[] numbers) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        
        stack.addFirst(0);
        
        int[] answer = new int[numbers.length];
        
        for (int i = 1; i < numbers.length; i++) {
            //현재 숫자보다 작은 애들은 현재가 제일 큰 수라고 볼 수 있음 다 빼서 현재 수를 뒷 큰수라고 기록
            while (!stack.isEmpty() && numbers[stack.peekFirst()] < numbers[i]) {
                answer[stack.removeFirst()] = numbers[i];
            }
            
            //가장 큰 수 인덱스를 넣어둠 
            stack.addFirst(i);
        }
        
        while (!stack.isEmpty()) {
            answer[stack.removeFirst()] = -1;
        }
        
        return answer;
    }
}