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

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

프로그래머스

 

N이 백만이기 때문에 O(N^2)으로 처리할 수 없다 혹은 O(NlogN)까지 최적화해야한다. 그러나 이분탐색으로 풀만한 여건을 안보이고 이중포문을 최적화해야하는 문제이다.

 

처음엔 스택을 생각하긴 했는데 구체적인 해결법을 생각하지는 못했다. 이 문제에서 파악했어야할 것은 다음과 같다.

 

9 2 1 1 6

 

이라고 주어졌을 경우 2, 1, 1 은 동일하게 6을 뒷큰수로 갖는다.

 

만약 이중포문으로 푼다면 2 -> 6 , 1 -> 6, 1 -> 6 으로 N^2번 돌지만 어떤 최적화를 해서 2, 1 , 1 을 한번에 6으로 정해주는 작업을 해줘야하는데 스택을 사용하게 된다.

 

1. 현재 스택의 top 보다 클 때 까지 스택에 넣는다.  stack = [1,1,2,9]

2. 6이 들어왔으므로 stack에서 하나씩 빼며 스택의 값과 6을 비교하여 6이 크면? 뒷큰수다. 이후엔 6,9가 스택이 될 것이다.

 

import java.util.*;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        Stack<num> stack = new Stack<>();
        
        for(int i = 0; i < numbers.length; i++){
            int idx = i; 
            int value = numbers[i];
            
            if(stack.isEmpty()) {
                stack.add(new num(idx, value));
            }else{
                while(!stack.isEmpty()){
                    int stkIdx = stack.peek().idx;
                    int stkValue = stack.peek().value;
                    
                    if(stkValue < value){
                        answer[stkIdx] = value;
                        stack.pop();
                    }else{
                        break;
                    }
                }
                stack.add(new num(idx, value));
            }
        }
        
        for(int i = 0; i < numbers.length; i++){
            if (answer[i] == 0) answer[i] = -1;
        }
        
        return answer;
    }
    
    static class num{
        int idx; 
        int value;
        
        public num(int idx, int value){
            this.idx = idx;
            this.value = value;
        }
    }
}