[Algorithm] 백준.17298 오 큰수

www.acmicpc.net/problem/17298

17298번: 오큰수

얼마전 라인 AD-platform 코딩테스트에서 나온 문제와 비슷한 유형의 문제.
100,000,000 이라는 범위때문에 여러 번 탐색하는 순간 시간초과가 발생한다는 것을 유의해서 접근했어야 했는데...

코딩테스트 문제는 오른쪽뿐 아니라 양쪽중에 가장 가까운 수를 출력하는게 목표였던 것 같다.

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

public class Main {

    static class Number {
        int idx;
        int score;

        public Number(int idx, int score) {
            this.idx = idx;
            this.score = score;
        }

    }

    static int N;
    static Stack<Number> stack = new Stack<>();
    static int[] answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        answer = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int next = Integer.parseInt(st.nextToken());
            PopBack(next);
            stack.push(new Number(i, next));
        }
        while (!stack.isEmpty()) {
            Number end = stack.pop();
            answer[end.idx] = -1;
        }
        StringBuilder sb = new StringBuilder();
        for(int num : answer){
            sb.append(num).append(" ");
        }
        System.out.println(sb.toString());

    }

    private static void PopBack(int next) {
        while (!stack.isEmpty()) {
            if (stack.peek().score < next) {
                Number end = stack.pop();
                answer[end.idx] = next;
                continue;
            }
            break;
        }
    }
}

한 방향으로 진행하는 것으로 답을 구해낼 때는 Stack을 잘 활용해보도록 하자!