백준 17298번 : 오큰수

 문제

www.acmicpc.net/problem/17298

17298번: 오큰수

17298 오큰수

 

 구현 방법

 오른쪽에 있으면서 A(i)보다 큰 수 중에 가장 왼쪽 수를 구해야합니다.

맨 초기 값을 스택에 넣어놓고 탐색을 시작했습니다.

스택의 값이 현재 값보다 작으면 내가 더 큰 값이므로 스택을 pop해주고 해당 값의 오큰수를 현재값으로 잡아주었습니다. 

이를 한번만 실행하면 오큰수를 찾지 못한 값들이 존재하므로 스택이 빌 때까지 반복문을 돌려주었습니다.

스택 값들이 현재 값보다 작으면 위와 같이 실행해주고 현재 값보다 크면 오큰수가 아니므로 break를 걸어 빠져나왔습니다.

현재 값도 오큰수를 찾아야하기 때문에 반복문이 끝난 후 현재 값을 스택에 push 해줍니다.

 

현재 수열을 저장할 때에는 출력할 때 입력했던 순서대로 출력해야 하기 때문에 오큰수의 값을 해당 인덱스 값에 같이 저장해주기 위해 2차원 배열을 사용해주었습니다.

 

 구현 코드

package BOJ.Gold;

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

public class B17298_오큰수 {
	static class nge {
		int i, value;

		public nge(int i, int value) {
			super();
			this.i = i;
			this.value = value;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		int[][] numbers = new int[N][2];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i=0;i<N;i++) {
			numbers[i][0] = Integer.parseInt(st.nextToken());
		}
		
		Stack<nge> stack = new Stack<>();
		stack.push(new nge(0, numbers[0][0]));
		for (int i=1;i<N;i++) {
			while(!stack.isEmpty()) {
				if (stack.peek().value<numbers[i][0]) {
					nge n = stack.pop();
					numbers[n.i][1] = numbers[i][0];
				} else break;
			}
			stack.push(new nge(i, numbers[i][0]));
		}
		
		while(!stack.isEmpty()) {
			nge n = stack.pop();;
			numbers[n.i][1] = -1;
		}
		
		for (int i=0;i<N;i++) {
			sb.append(numbers[i][1]+" ");
		}
		System.out.println(sb);
	}
}

 

정답!