[BOJ-JAVA] 17298번: 오큰수

문제

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

17298번: 오큰수

수열에 주어질 때 각 인덱스를 기준으로 가장 오른쪽에 있는  인덱스의 수보다 큰 수를 찾는 문제이다.

 

문제 풀이

2차원 배열을 사용해서 푸는게 가장 쉬운 방식이지만 시간초과가 날 것이기 때문에 자료구조를 적절히 활용해야한다. stack을 사용해 문제를 해결하는 것까지는 확인을 했지만 stack을 어떻게 활용해야하는지 고민했던 문제이다. 

초반에는 수열의 뒤에서부터 확인하며 오큰수를 찾는 방법을 구하려 했지만 해결되지 않았고, 수열의 앞부터 확인하는 방식으로 방법을 바꾸며 해결했다.

 

수열의 앞에서 부터 확인하며 큰 수를 만났을 때 이전 수의 오큰수를 큰 수로 바꿔주는 방식이다. 즉, stack에는 큰수를 만나기까지 인덱스를 저장해두는 용도로 쓰인다. 큰수를 찾으면 stack에 담긴 인덱스들의 수와 큰 수를 비교하여 오큰수를 바꿔준다.  

수열을 다 돌았을 때 stack의 남아있는 인덱스들은 오큰수를 찾지 못했다는 것이기 때문에 -1로 오큰수를 바꿔준다.

 

1. 수열의 처음부터 끝까지 확인
   1. 스택이 비었거나, stack.peek의 값이 현재 값보다 크다면 stack에 현재 index를 push
   2. stack.peek가 현재 값보다 작다면 오큰수를 찾은 것
      1. peek의 idx의 오큰수를 현재 값으로 변경 
   3. 2번이 아닐 때까지 반복
2. stack이 비어있지 않다면, 오큰수를 찾지 못한 수들
   1. stack에 담긴 index의 오큰수를 -1로 변경 

 

Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.valueOf(br.readLine());
        String[] line = br.readLine().split(" ");
        int[] arr = new int[line.length];
        for(int i=0; i< line.length; i++) {
            arr[i] = Integer.valueOf(line[i]);
        }
        Stack<Integer> stack = new Stack<>();
        for(int i=0; i< arr.length; i++) {
            while(!stack.empty() && arr[i] > arr[stack.peek()]) {
                int idx = stack.pop();
                arr[idx] = arr[i];
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int idx = stack.pop();
            arr[idx] = -1;
        }
        StringBuilder sb = new StringBuilder();
        for(int num: arr) {
            sb.append(num).append(" ");
        }
        System.out.println(sb);
    }
}