백준 17298 - 오큰수

문제 파악

수열 A가 주어졌을 때 A의 각 원소에 대해 오큰수를 구하는 문제

오큰수 : 현재 수 보다 오른쪽에 있으면서 가장 왼쪽에 있는 큰 수
만약 없으면 -1 반환

스택을 활용 : 오큰수를 못 찾은 숫자의 인덱스를 스택에 하나씩 저장해서 인덱스가 넘어갈 때마다 스택의 맨 위에 있는 인덱스의 값이랑 비교해 다음 수가 더 크면 그것을 오큰수로 지정!

풀이

1. 수열 개수 N을 입력 받는다.
2. N개의 수열 A를 하나씩 입력 받는다.
3. 반복문을 돌려가며 스택을 활용한다.
   a. 처음에 스택이 비어 있으므로 0을 삽입
   b. 다음 인덱스로 넘기기
   c. A[1]의 값과 스택의 가장 위에 있는 인덱스의 값과 비교
   d. A[1] > A[0]이면 0을 pop
   e. A[1]의 값을 새로운 배열 result에 삽입

코드

import java.util.Scanner;
import java.util.Stack;

public class b17298 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 수열의 길이
        int[] arr = new int[n]; // 원본 수열
        int[] result = new int[n]; // 결과 수열
        Stack<Integer> stack = new Stack<>(); // 인덱스를 저장

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            // 현재 수가 스택에 있는 인덱스의 수보다 크면, 오큰수로 기록
            while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
                result[stack.pop()] = arr[i];
            }
            stack.push(i);
        }

        // 아직 남은 인덱스들은 오큰수를 못 찾았다는 뜻 → -1
        while (!stack.isEmpty()) {
            result[stack.pop()] = -1;
        }

        // 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(result[i]).append(" ");
        }
        System.out.println(sb.toString());
    }
}