156. 17298(오큰수) - 자바

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

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

		String[] S = br.readLine().split(" ");
		for (int i = 0; i < N; i++) {
			result[i] = -1;
			A[i] = Integer.parseInt(S[i]);
		}

		for (int i = 0; i < N; i++) {
			try {
				while (A[stack.get(stack.size() - 1)] < A[i]) {
					result[stack.pop()] = A[i];
				}
			} catch (Exception e) {

			}
			
			stack.add(i);
		}

		for (int val : result) sb.append(val).append(" ");
		
		System.out.println(sb);
	}
	
}

문제요약

입력값에 오큰수를 구해라.

오큰수란?

A=A1 ~ AN이 있을 때 Ai번째의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중 가장 왼쪽에 있는 수이다.

다시 말해 지금 수 보다 크고, 인덱스 크기가 가장 작은 수 

설명

입력 예시로

백준에 있는 다음과 같은 예시를 들어보자.

3과 5를 비교했을 때 5가 더 크다. 따라서 답은 5가 된다.

답이 7이 될 수 없는 이유는 오큰수는 N보다 오른쪽에 있으면서 가장 왼쪽에 있는 수이다.

다음 5는 먼저 2보다 크다 그래서 2가 될 수 없고 7은 5보다 크기 때문에 가능하다.

2도 7이 더 크기 때문에 7이 나온다.

7의 오른쪽에는 수가 없을 뿐만 아니라 7보다 더 큰 수도 없기 때문에 -1이 나온다.

따라서 답은 5 7 7 -1이다.

전체적인 맥락은 이렇다.

 

		for (int i = 0; i < N; i++) {
			result[i] = -1;
			A[i] = Integer.parseInt(S[i]);
		}

먼저 모두 오큰수가 없는 경우인 -1로 초기화 했다.

초기화 하는 김에 입력값도 같이 받았다.

			try {
				while (A[stack.get(stack.size() - 1)] < A[i]) {
					result[stack.pop()] = A[i];
				}
			}

stack에 값이 없다면 에러를 불러 일으킬 것이다.

그것을 이용하여 try / catch문을 사용했다.

 

A[stack.get(stack.size() - 1)]이 기준이다.

기준을 중심으로 오른쪽의 크기 A[i]가 크다면 while문을 계속 진행한다.

 

result에 stack 값을 꺼내 인덱스로 정하고, 크기가 더 큰 오른쪽 값을 집어 넣는다.

catch (Exception e) {

			}
			
			stack.add(i);

try except문이 종료되면 stack에 i값을 집어넣는다.

아직 i번째의 오큰수를 구하지 않았기 때문이다.

 

		for (int val : result) sb.append(val).append(" ");
		
		System.out.println(sb);

for문을 이용하여 값을 StringBuilder에 넣어 주었다.

바로 출력하지 않는 이유는 system.out.print는 생각보다 시간을 많이 잡아먹는다.

따라서 바로 출력하면 시간초과가 발생하기 때문에 sb에 저장하고 sb를 출력하는 방식을 채택하였다.