b.17298 오큰수

 

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

 

 

 

이 문제는 배열의 각 원소에 대해

"오큰수(오른쪽에 있는 수 중 현재 수보다 큰 수 중 가장 가까운 것)"를 구하는 문제다.

먼저 main 메서드에서 프로그램 실행의 흐름을 살펴보면,

사용자로부터 입력값을 받아 배열에 저장한 후 logic 메서드를 호출해

오큰수를 계산한 뒤 결과를 출력한다.

사용자는 먼저 배열의 크기 N을 입력하고,

다음 줄에 배열의 원소를 공백으로 구분하여 입력한다.

이후 logic 메서드를 호출하여 오큰수를 계산한다.

 

logic 메서드는 스택을 사용하여 효율적으로 오큰수를 구하는 핵심 부분이다.

이 알고리즘은 반복문을 통해 배열을 순회하면서

현재 원소와 스택에 저장된 인덱스를 비교한다.

 

스택에는 아직 오큰수가 결정되지 않은 인덱스들만 저장되고,

현재 배열의 원소가 스택의 맨 위에 있는 인덱스에 해당하는 배열 값보다 크다면,

스택의 맨 위 인덱스를 꺼내고 해당 인덱스 위치에 현재 배열의 원소를 오큰수로 설정한다.

 

이 과정은 스택이 비거나 현재 원소가 스택에 있는 값보다 작을 때까지 반복된다.

이후, 현재 인덱스를 스택에 추가하여 다음 비교를 준비한다.

모든 반복이 끝난 뒤에도 스택에 남아 있는 인덱스들은 오른쪽에 자신보다 큰 수가 없다는

것을 의미한다. 따라서 이러한 인덱스들에 대해 배열 값으로 -1을 설정한다.

 

최종적으로, logic 메서드 실행이 끝나면 배열

numbers에는 각 원소의 오큰수가 저장되어 있다.

 

 

import java.io.*;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[] numbers;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        numbers = new int[N];
        for (int i = 0 ; i < N ; i++){
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        logic();

        sb = new StringBuilder();
        for (int i = 0 ; i < N ; i++){
            sb.append(numbers[i]).append(" ");
        }

        System.out.println(sb);
    }

    private static void logic() {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < N; i++) {
            while(!stack.isEmpty() && numbers[i] > numbers[stack.peek()]) {
                numbers[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }

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