boj 17298 오큰수

www.acmicpc.net/problem/17298

17298번: 오큰수

스택으로 구현할 수 있고, 시간초과에 주위해야하는 문제입니다.

자바에서는 출력만으로도 시간초과가 나올 수 있기때문에 반복적인 System.out.println 보다는

StringBuffer, StringBuilder, BufferedWriter 중에서 사용해야합니다.

 

우선 오큰수는 자신의 오른쪽에 있는 숫자들 중에서 자신보다 큰 수 중에 가장 왼쪽에 있는 수를 말합니다.

 

저는 이 문제를 해결하기 위해 수열의 역순으로 탐색을 하였습니다.

list[i]를 스택에 넣기 전에 자신보다 작은 값들을 전부 pop해준 후에 남아있는 스택의 top에 있는 값이 오큰수 입니다.

 

먼저 스택이 비어있다면 자신이 가장 큰 수이므로 -1입니다.

비어있지 않다면 스택의 top이 오큰수입니다.

 

이 값들을 StringBuffer에 다 append를 해준 후에 마지막에 sb.toString()을 출력해주시면 되겠습니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Stack<Integer> s = new Stack<>();
    static int list[], ans[];
    static int N;
 
    static void print() {
        for (int i = 0; i < N; i++) {
            sb.append(ans[i] + " ");
        }
 
        System.out.println(sb.toString() + "\n");
    }
 
    static void func() {
        for (int i = N - 1; i >= 0; i--) {
            while (!s.isEmpty() && s.peek() <= list[i])
                s.pop();
 
            if (s.isEmpty())
                ans[i] = -1;
            else
                ans[i] = s.peek();
 
            s.add(list[i]);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
        ans = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}