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

문제

풀이

• 스택을 선언하고 스택의 top에 있는 원소와 numbers 원소와 크기를 비교한다
• 스택 top 보다 수가 크다면 조건을 만족하므로 numbers보다 작다는 조건을 만족하는 스택안의 원소들은 모두 pop하면서 큰 수를 저장할 수 있다.

유의할 점

• 단순 비교(O(N^2)) 로 풀지 못할 때 내가 떠올리는 풀이는 인덱스트리와 투포인터 밖에 없는 거 같다. 좀 더 고민을 많이 해볼 것

• 풀이를 나중에 떠올렸음에도 스택에 인덱스가 아닌 값을 넣어서 이걸 어떻게 처리하나 고민했었다. 그냥 인덱스를 넣으면 인덱스 값과 배열 값도 알 수 있는데

코드

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