[JAVA] 백준 17298 오큰수

https://www.acmicpc.net/problem/17298

 

문제분석

스택에 "인덱스" 를 저장하면서 문제를 해결해야 한다.

기준 인덱스 i와, 스택에 저장된 인덱스들이 있다. 편의상 배열을 arr이라고 부르면, 흐름을 아래와 같이 설명할 수 있다.

 

i는 "오큰수 후보" 인덱스 라고 볼 수 있다. 그리고 "오큰수를 정해야 하는 인덱스들" 이 바로 스택에 저장된 인덱스들이다.

만약 "오큰수 후보" 가 "오큰수를 정해야 하는 인덱스들" 의 peek값보다 크지 않다면, 해당 오큰수 후보는 스택에 저장되고, i++가 된다.

(왜냐하면, '오른쪽에 있는 큰 수 중에 가장 나와 가까운 수' 이기 때문이다.)

 

 

if(스택이 비었다면) -> {stack.push(i); i++;}

else(스택이 비어있지 않다면)->

        if(arr[i] > arr[스택.peek]) -> arr[스택.pop] = arr[i];

        else -> {stack.push(i); i++;}

 

pseudo 코드를 작성하고 보니, 더 줄일 수 있었던 것 같다.

 

 

 

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] arr = Arrays.stream(br.readLine().split(" "))
                            .mapToInt(Integer::parseInt)
                            .toArray();// 수열 저장하는 배열
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        
        int i = 0;
        while(i < N){
            if(stack.isEmpty()){
                stack.push(i);
                i += 1;
            }else{
                // 스택에 뭐 있으면, peek로 확인한 맨 위 index 값이랑 i 값이랑 비교해야 함.
                // if 스택 peek의 숫자보다 i 인덱스의 숫자가 더 크면, 스택에서 pop한 뒤 arr[i]를 pop한 index에 초기화
                // else 스택 peek 숫자가 i 보다 크다면, stack에 i를 push
                if(arr[stack.peek()] < arr[i]) arr[stack.pop()] = arr[i];
                else{
                    stack.push(i);
                    i += 1;
                }
            }
        }
        while(!stack.isEmpty()) arr[stack.pop()] = -1;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(i = 0; i < arr.length; i++){
            bw.write(String.valueOf(arr[i]));
            if(i < arr.length - 1) bw.write(" ");
        }
        bw.flush();
        bw.close();
    }
}