[BOJ 17298] 오큰수 (Java)

문제

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

17298번: 오큰수

 

풀이

Stack을 이용 풀었다. 

뒤에서부터 순회하며 Stack에 넣을건데

먼저 Stack의 top을 체크하면서 현재 원소보다 작으면 pop을 해준다. (현재 원소 보다 큰 값이 나올때까지)

이후 Stack이 empty 상태라면 현재 원소보다 큰 수가 없는 것이므로 -1을 저장 

Stack의 사이즈가 1이상이라면 Stack의 top이 현재 원소의 오큰수이므로 저장한다.

마지막으로 현재 원소를 Stack에 넣는다.

 

시간 초과 문제로, 출력에 신경을 써야한다.

뒤에서부터 순회를 하기 때문에 StringBuilder의 insert(0, 답 + " ")로 문자열을 생성했는데 시간 초과가 발생한다.

로직 변경 없이 답을 배열에 담은 후 따로 for문을 추가하여 append(답).append(" ") 코드로 바꿔줬더니 해결되었다.

 

소스코드

package stack;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ17298 {
    public static void main(String[] args) throws Exception{
        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+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<Integer> stack = new Stack<Integer>();

        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = N; i >= 1; i--){
            int num = arr[i];
            while(!stack.isEmpty() && stack.peek() <= num){
                stack.pop();
            }
            if(stack.isEmpty()) arr[i] = -1;
            else arr[i] = stack.peek();
            stack.push(num);
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= N; i++){
            sb.append(arr[i]).append(" ");
        }
        bw.write(sb.toString());
        bw.flush();
    }
}