Programmers - 뒤에 있는 큰 수 찾기 with JAVA (V)

 

문제

예를 들어, [1, 2, 3, 4, 5] 가 있을 때, 해당 수보다 뒤에있으면서 가장 가깝고 해당 수보다 큰 수를 구하고 없으면 -1을 넣은 결과를 출력하라.

 

 

 

 

로직

1. 결과를 모두 -1로 초기화한다.

2. 스택에 해당 인덱스 값을 순차적으로 넣는다.

3. 스택 마지막부터 확인하면서(후입 선출) 현재 값보다 꺼낸 인덱스에 해당하는 값이 작다면 스택에서 해당 수를 빼고 결과를 현재 값으로 설정함을 반복한다. (만약, 전의 값이 크다면 종료)

4. 위의 과정을 반복한다.

 

대략 시간 복잡도는 O(N)에 가능하다.

 

 

예시 : [9, 1, 5, 3, 6, 2]

Stack - Value - result

[0] - [9] - [-1, -1, -1, -1, -1, -1]

[0, 1] - [9, 1] - [-1, -1, -1, -1, -1, -1]

[0, 2] - [9, 5] - [-1, 5, -1, -1, -1, -1]

[0, 2, 3] - [9, 5, 3] - [-1, 5, -1, -1, -1, -1]

[0, 4] - [9, 6] - [-1, 5, 6, 6, -1, -1]

[0, 4, 5] - [9, 6, 2] - [-1, 5, 6, 6, -1, -1]

 

 

코드

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Arrays.fill(answer, -1);
        Stack<Integer> indexes = new Stack<>();
        for(int index=0; index<numbers.length; index++){
            int number = numbers[index];
            while(true){
                if(indexes.size() == 0){
                    break;
                }
                int now_index = indexes.pop();
                if(numbers[now_index] < number){
                    answer[now_index] = number;
                }
                else{
                    indexes.add(now_index);
                    break;
                }
            }
            indexes.add(index);
        }
        return answer;
    }
}