[BOJ] 17298번 오큰수 (Java/Stack)

문제

백준 17298번 오큰수

---

풀이1

1. 해당하는 인덱스에 오큰수를 출력하기 위해 인덱스와 숫자값을 가지는 Element 클래스를 이용합니다.
2. 오큰수가 없을 경우 -1을 출력해야 하므로, 오큰수를 저장하는 res 배열의 원소를 전부 -1로 초기화합니다.
3. 스택의 top보다 현재 입력받는 수가 크면, 현재 수는 스택의 top의 오큰수입니다.
4. 스택의 top의 인덱스에 현재 수(=오큰수)를 저장하고, pop하여 제거합니다.
5. 스택이 비어있지 않고, 현재 수가 스택의 top보다 크면 3, 4번 과정을 반복합니다.
6. 스택에 현재 수를 push 합니다.
7. 모든 수를 입력받으면 for문이 종료되고, res 배열에서 오큰수를 하나씩 출력합니다.

소스 코드

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

public class Main {
	static class Element {
		int idx, num;

		public Element(int idx, int num) {
			super();
			this.idx = idx;
			this.num = num;
		}

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		int res[] = new int[N]; // 출력 결과 입력하는 배열
		Arrays.fill(res, -1); // 초기값을 -1로 설정

		Stack<Element> stack = new Stack<>();

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

			while (!stack.isEmpty()) {
				if (stack.peek().num < cur) { // 현재 수가 스택의 top보다 크면 현재 수가 오큰수
					res[stack.peek().idx] = cur; // 스택의 top 배열의 인덱스에 오큰수(=현재 수)를 넣어주고
					stack.pop(); // 스택의 top을 pop해서 제거함
				} else {
					break; // 현재 수가 오큰수가 아니면 반복문 종료하고 현재 수를 스택에 push 함
				}
			}

			stack.push(new Element(i, cur));
		}

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

		System.out.println(sb.toString());

	}

}

---

풀이2

주어진 숫자를 모두 입력받은 후 배열의 뒤에서부터 탐색하는 방법입니다.

1. arr 배열에 N개의 수열을 입력받습니다.
2. 오큰수를 구하기 위해 사용할 stack 스택과, 결과를 저장할 res 스택을 선언합니다.
3. 배열의 맨 뒤에서부터 탐색을 시작합니다.
4. stack 스택이 비어있지 않고, 스택의 top보다 현재 탐색 중인 수가 크면 스택에서 제거하는 과정을 반복합니다.
5. 4번 과정 반복 후 스택이 비어있지 않으면 스택의 top이 현재 탐색 중인 수의 오큰수이므로 res 스택에 push 합니다.
6. 4번 과정 반복 후 스택이 비어있으면 현재 탐색 중인 수의 오큰수는 없으므로 res 스택에 -1을 push 합니다.
7. 현재 탐색 중인 수를 stack에 push 합니다.
8. 4~7번 과정을 N번 반복 후 res 스택에 저장된 오큰수를 출력합니다.

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
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));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		int arr[] = new int[N];
		Stack<Integer> stack = new Stack<>();
		Stack<Integer> res = new Stack<>();

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

		for (int i = N - 1; i >= 0; i--) {
			while (!stack.isEmpty() && arr[i] >= stack.peek()) {
				stack.pop();
			}

			if (!stack.isEmpty()) {
				res.push(stack.peek());
			} else {
				res.push(-1);
			}

			stack.push(arr[i]);
		}

		for (int i = 0; i < N; i++) {
			sb.append(res.pop()).append(" ");
		}
		System.out.println(sb.toString());

	}

}