[백준 17928] 오큰수[java]

문제

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

17298번: 오큰수

---

해결 방법

 

스택을 어떻게 활용해야 할지 어려운 문제였다.

 

스택을 쓰지 않고 풀 수 있을거 같아서 풀고 제출했는데... 정답이 틀렸다니...

위의 이유로 스택을 활용하는 방법에 대해서 고민해봤습니다.

 

stack 활용

1. 배열의 index를 스택의 원소로 이용합니다.

2. for문을 0부터 n-1까지 반복합니다. 0~n-1 -> i

3. while문을 사용하고 스택이 비어있지 않고 stack.peek값보다 arr[i]의 값이 클때까지 반복합니다.

4. while문안에서는 stack의 값을 pop하면서 그 값을 배열의 index로 하여 arr[i]의 값을 넣어줍니다.

5. while문에 나와서 혹은 들어가지 않을 경우 stack에 i를 추가합니다.

6. 마무리로 stack에 남아있는 값은 배열의 처리하지 못한 index값이므로 -1을 넣어주면 됩니다.

 

코드

package stack;

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

// 3 5 2 7
// 5 7 7 -1
public class Baek17298 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int cnt = scan.nextInt();
        int[] arr = new int[cnt];
        Stack<Integer> stack = new Stack<>();


        for(int i = 0; i<cnt;i++){
            arr[i] = scan.nextInt();
        }

        for(int i = 0; i<cnt;i++){

            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                arr[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

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

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<arr.length;i++){
            sb.append(arr[i]).append(' ');
        }

        System.out.println(sb);

    }
}