[백준 골드 4] 17298번: 오큰수

문제

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

17298번: 오큰수

 

풀이

• 크기가 N인 수열 A가 있을 때, 각 원소 Ai에 대하여 Ai보다 오른쪽에 있으면서 큰 수 중에서 가장 왼쪽에 있는 수를 오큰수라고 한다.
• 수열 A가 있을 때, 각 원소들의 오큰수를 구해야 한다. 오큰수가 없다면 -1을 출력한다.
• 수열 A의 길이와 각 원소의 크기는 둘 다 1 이상 1,000,000 이하이다. 즉, 다중 for문을 사용한다면 무조건 시간 초과가 일어난다.

스택의 원리를 이해하고 이를 적용하는 방법을 묻는 문제이다. 스택은 LIFO (Last In First Out), 즉 제일 나중에 들어온 원소가 가장 빨리 나가는 특징을 가지고 있다.

 

스택에는 수열의 인덱스를 저장하면서 인덱스에 해당하는 원소의 오큰수를 구한다.

수열을 탐색하면서 스택의 top에 위치한 원소와 현재 수열의 원소를 비교한다.

현재 수열의 원소가 스택의 원소보다 크다면, 현재 수열의 원소가 스택의 원소의 오큰수가 되는 것이다.

이 조건을 만족하는 경우 계속 반복하면서 스택에서 pop 해준다.

만약 스택이 비어있거나, 현재 수열의 원소가 스택의 top에 위치한 원소보다 작아 오큰수의 조건을 만족하지 못한다면, 현재 수열의 원소에 해당하는 인덱스를 스택에 push하고 다음 원소를 탐색한다.

for (int i = 0; i < N; i++) {
    /*
     * 스택이 비어있지 않고, 현재 원소가 스택 맨 위의 원소보다 큰 경우 
     * 오큰수의 조건을 만족하므로가능한 한 계속 pop하면서 stack에
     * 저장된 인덱스에 해당하는 원소를 현재 원소(오큰수)로 바꾸어 준다.
     */
    while (!stack.isEmpty() && A[stack.peek()] < A[i])
        NGE[stack.pop()] = A[i];

    stack.push(i);
}

 

그리고 수열의 모든 원소를 탐색하였을 때, 스택에 남은 원소들은 오큰수가 존재하지 않는 경우이다.

모두 -1로 바꾸어 준다.

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

 

 

전체 코드(Java)

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] A = new int[N];
		int[] NGE = new int[N];
		Stack<Integer> stack = new Stack<>();

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			while (!stack.isEmpty() && A[stack.peek()] < A[i])
				NGE[stack.pop()] = A[i];

			stack.push(i);
		}

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

		for (int n : NGE) {
			sb.append(n).append(" ");
		}
		
		System.out.println(sb.toString());
	}
}

 

후기

풀이 결과를 보면 별 것 없어 보이지만, 스택을 잘 이해하고 문제에 적용하는 방법, 그리고 과정을 떠올리는 방법이 어려웠던 것 같다.