[백준(Baekjoon)][자바(java)] 17298 : 오큰수 / 스택

 

www.acmicpc.net/problem/17298

17298번: 오큰수

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
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 IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		int n = Integer.parseInt( br.readLine() );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int a[] = new int[n], r[] = new int[n], i;
		for( i = 0; i < n; i++ ) 
			a[i] = Integer.parseInt( st.nextToken() );
		br.close();
		
		Stack<Integer> s = new Stack<>();
		for( i = n-1; i >= 0; i-- ) {
			while( !s.isEmpty() && s.peek() <= a[i] )
				s.pop();
			r[i] = s.isEmpty() ? -1 : s.peek();
			s.push( a[i] );
		}

		StringBuilder sb = new StringBuilder();
		for( int rr : r ) 
			sb.append( rr + " " );
		System.out.println( sb.toString() );
	}
}

 

*  스택

-  입력받은 배열 a와 같은 크기의 배열 r 생성
-  배열 a를 역순으로 탐색
-  스택의 top이 a[i]보다 작거나 같으면 pop 한다
-  스택이 비었으면 오큰수는 -1, 그렇지 않으면 top이 a[i]의 오큰수( r[i] )가 된댜
-  스택에 a[i]를 넣고 루프 반복