BOJ - 17298 오큰수

17298 오큰수 : https://www.acmicpc.net/problem/17298

---

Problem

---

Solve

수열에서의 각 값의 오른쪽에 있는 수 중 해당 값보다 크고 왼쪽에 위치한 값을 반환하는 문제.

문제 풀이 순서는 아래와 같다.

1. 각 수열의 오큰수를 저장할 int[] answer를 -1로 초기화, 수열을 저장할 int[] arr 초기화, 수열값의 index를 저장할 stack.
2. 각 수열의 값을 저장하기 전에 stack에 저장하려는 현재 수열의 값 > arr[stack.peek()] 이면 현재 수열의 값은 arr[stack.peek()]의 오큰수가 되므로 answer[stack.pop()] = '현재 수열의 값'으로 저장한다.
   • 해당 프로세스를 arr[stack.peek()]가 현재 수열의 값까지 클때까지 반복한다.
   • 모든 수열을 stack에 넣을때까지 반복.

즉, stack은 오큰수를 구하지 못한 수열 값의 index 순서대로 저장하고 있다.

---

Code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class 오큰수 {
	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());
		int[] arr = new int[N];
		int[] res = new int[N];

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

		//오큰수를 구하지 못한 arr의 idx
		Stack<Integer> stack = new Stack<>();
		for (int idx = 0; idx < N; idx++) {
			if(stack.isEmpty()){
				stack.push(idx);
			}else{
				//stack에 있는 수들의 예비 오큰수
				int currentNum = arr[idx];

				//stack에 있는 수들과 예비 오큰수와 비교한다.
				while(!stack.isEmpty()){
					//예비 오큰수가 더 크다면 stack에 있던 해당 수의 오큰수는 currentNum이다.
					if(arr[stack.peek()] < currentNum){
						res[stack.pop()] = currentNum;
					}else{
						//해당 stack 수의 오큰수가 아니라면 나머지 stack의 값의 오큰수도 아니다.
						break;
					}
				}
				stack.push(idx);
			}
		}

		StringBuilder sb = new StringBuilder();
		for(int i=0;i<N;i++){
			sb.append(res[i]);
			sb.append(" ");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

다시 풀어보니 arr배열 앞이아닌 뒤에서 부터 접근하여 arr[i] < stack.peek()일 때 answer[i] = stack.peek()으로 오큰수를 구해주고, arr[i] >= stack.peek()일 때 stack.pop()을 하며 해당 수열 값의 오큰수를 찾고 찾지 못하면 -1을 넣어주었다.

즉, 두번째 풀이에서는 stack을 오큰수를 구하지 못한 수가 아닌 오큰수 후보(?)를 저장해 구현했다.

public class 오큰수_V2 {
	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());
		int[] num = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i=0;i<N;i++){
			num[i] = Integer.parseInt(st.nextToken());
		}

		int[] answer = new int[N];
		Stack<Integer> stack = new Stack<>();
		for(int i=N-1;i>=0;i--){
			if(stack.isEmpty()){
				stack.push(num[i]);
				answer[i] = -1;
			}else{
				while(!stack.isEmpty() && stack.peek()<=num[i]){
					stack.pop();
				}
				if(!stack.isEmpty()){
					answer[i] = stack.peek();
				}else{
					answer[i] = -1;
				}
				stack.push(num[i]);
			}
		}

		StringBuilder sb = new StringBuilder();
		for(int i=0;i<N;i++){
			sb.append(answer[i]);
			sb.append(" ");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference