문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java

구현방법

이 문제를 풀기위해서 필요하다고 생각한 것은 숫자들의 index 위치와 값이 필요하고 각 숫자에 대해서 2중 for문을 돌릴경우 제시된 자료의 최대값인 100만개의 자료가 들어갈 경우 10초는 그냥 넘어가기 때문에 Stack을 이용해서 현재위치의 값과 stack의 맨위의 있는 값을 비교해서 현재위치의 값이 더 큰 경우 stack의 값을 pop()을하고 stack에 들어있는 그전 값들도 쭉 비교를 해주면서 현재위치이 더 큰 경우에는 각 숫자의 index위치에 현재 위치의 값을 적어줍니다.

만약 끝까지 다돌았는데 stack에 값이 남아있는 경우는 그 값보다 뒤에 있는 수중 큰값이 존재하지않다는 것을 의미하기 때문에 그 값이 들어있는 index에 -1을 넣어줍니다.

구현알고리즘

Stack

CODE

import java.util.Stack;

class Solution {
    //위치와 숫자를 파악하기 위한 check 클래스
    class check{
        int idx;
        int number;

        check(int idx,int number){
            this.idx = idx;
            this.number = number;
        }
    }

    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        //비교를 위한 stack
        Stack<check> stack = new Stack<>();


        for(int index = 0 ;index <numbers.length;index++){
            //값이 없을 경우 push를 하고 다음 숫자로 진행
            if(stack.isEmpty()){
                stack.push(new check(index,numbers[index]));
                continue;
            }
            //stack의 맨위의 값이 현재위치의 숫자보다 작은경우
            if(stack.peek().number < numbers[index]){
                //현재 위치의 값들뿐만아니라 그 전에 stack에 들어있는 값들도 비교해서
                //stack에 들어있는 값들이 작은경우 그 값을 pop하고 idx위치에 현재 숫자를 적는다.
                while(!stack.isEmpty()&&stack.peek().number < numbers[index]){
                    check check_number = stack.pop();
                    answer[check_number.idx] = numbers[index];
                }
                stack.push(new check(index,numbers[index]));
                //stack의 맨위의 값보다 작거나 같은경우 push
            }else {
                stack.push(new check(index,numbers[index]));
            }
        }
        while(!stack.isEmpty()){
            check result = stack.pop();
            answer[result.idx] = -1;
        }
        return answer;
    }
}