[JAVA][백준][G4] 오큰수

 

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

 

📒 문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

● 시간 제한 / 메모리 제한

 1 초 / 512 MB 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

입출력 예

# 입력1
4
3 5 2 7

# 출력1
5 7 7 -1

# 입력2
4
9 5 4 8

# 출력2
-1 8 8 -1

 

알고리즘 분류

• 자료 구조
• 스택

---

💻 소스코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 풀이 시작
        int N = Integer.parseInt(br.readLine()); // 수열 크기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] A = new int[N]; // 수열 배열
        for(int i = 0 ; i < N ; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

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

        for(int i = 0 ; i < N; i++){
            if(result[i] == 0) result[i] = -1;
            bw.write(result[i] + " ");
        }

        bw.flush();
        bw.close();
    }
}

 

📝 풀이

해당 문제는 스택을 이용해서 문제를 해결했다.

 

문제 풀이의 핵심 아이디어는 아래 두가지이다.

• 스택에 인덱스를 저장한다.
• 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.

A[stack.peek()] 이런식으로 스택의 인덱스를 이용해 수열의 값을 파악하고 새로 들어온 수랑 비교하면된다.

만약 오큰수가 된다면 result[stack.pop]을 통해 결과에 맞는 인덱스에 오큰수를 넣어줄 수 있다.

 

[자료구조] 스택 (Stack)