뒤에 있는 큰 수 찾기

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

프로그래머스

 

 

소스코드

import java.util.Stack;

class Solution {
    class Node {
        int v,o;

        public Node(int v, int o) {
            this.v = v; //값
            this.o = o; //순서
        }
    }
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Node> s = new Stack<>();
        for (int i = 0; i < numbers.length; i++) {
            while (!s.isEmpty()) {
                if (s.peek().v < numbers[i]) {
                    Node pop = s.pop();
                    answer[pop.o] = numbers[i];

                } else break;
            }
            s.add(new Node(numbers[i], i));
        }
        while(!s.isEmpty()) {
            Node pop = s.pop();
            answer[pop.o] = -1;
        }
        return answer;
    }
}

 

 

해결방법

Stack을 사용하였다. 입력받은 배열의 요소들을 차례로 스택에 넣어주었다. 스택에 들어오는 값이 들어있는 값들보다 크다면 들어있는 값들과의 비교를 통해 빼주고 저장하였다. 그냥 뺄 경우 해당 값이 원래 어디에 위치하는지 모르기에 Push할 때 값, 순서를 가진  Node 객체를 생성하여 넣어주었다. 마지막으로 스택에 남아있는 값들은 뒷 큰수가 없는 값들이므로 모두 빼주어 제 순서에 맞게 -1로 저장하였다.