백준 17298 오큰수 java

처음에 내가 생각했던 방법은 스택을 이용하나 stack의 peek값을 int target로 따로 저장해두고 target보다 작은 경우에는 pop으로 스택에서 지워주는 방법이었음

 

책에 나와있는 풀이를 보니 stack에 arr의 요소 값을 넣는 대신에 인덱스를 넣어서 다음값이 큰 경우에만 loop를 돌도록 했다. loop를 전부 돌고도 스택이 비어있지 않은 것은 arr를 다 돌도록 현재 값보다 큰수가 없어 stack.push 해주고 남은 수이므로 일괄적으로 -1로 정해준다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] result = new int[N];

        String[] str = br.readLine().split(" ");
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(str[i]);
        }
        
        //stack 초기화
        stack.push(0);
        for(int i = 1; i < N; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

        while(!stack.isEmpty()){
            result[stack.pop()] = -1;
        }


        for(int i = 0; i < N; i++){
            bw.write(result[i] + " ");
        }
        bw.flush();
        bw.close();
    }