백준 - 오큰수 ( 17298번, JAVA )

Stack ( https://www.acmicpc.net/problem/17298 )

풀이

• 문제가 인덱스와 스택을 잘 활용해야했다.. 3, 5, 2, 7을 기준으로 예를 들어보자
  -> 3에 해당하는 인덱스 0을 스택에 저장
  -> 스택에 상단 인덱스에 해당하는 값이 현재 기준이 되는 값보다 작다면
  -> 인덱스 스택[0] = 3 < arr[1] = 5 조건에 만족하기 때문에 스택에 최상단 0을 빼고 해당하는 값 5를 answer[0] 에 넣는다.
  -> 인덱스 스택에 i(1)을 넣는다.
  -> 인덱스 스택[1] = 5 < arr[2] = 2 조건에 만족하지 않기 때문에 스택에 i(2)만 저장
  -> 인덱스 스택[1,2] = 2 < arr[3] = 7 조건에 만족하기 때문에 스택에 최상단 2을 빼고 해당하는 값 7을 answer[2]에 넣는다.
  -> 인덱스 스택[1] = 5 < arr[3] = 7 조건에 만족하기 때문에 스택에 최상단 1을 빼고 해당하는 값 7을 answer[1]에 넣는다.
  -> 인덱스 스택에 i(3)을 넣는다.
  -> 만약 스택이 비어있지 않다면 오큰수가 없기에 인덱스 3에 해당하는 부분에 -1을 넣는다

이거 인덱스+스택 활용하는 대표문제 같으니 꼭 기억해서 다른문제 활용하자😃

package problem_solving.stack;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;

public class BaekJoon_17298 {
	public static void main(String[] args ) {

		Scanner sc = new Scanner(System.in);
		int  n = Integer.parseInt(sc.next());
		int [] arr = new int[n];
		Stack<Integer> st = new Stack<>();
		for(int i = 0 ; i < n ; i++) {
			int num = Integer.parseInt(sc.next());
			arr[i] = num ; 
		}
		int [] answer  = new int[n];
	
		
		for(int i= 0 ; i  < n ; i ++) {
			
			while( !st.isEmpty() && arr[st.peek()] < arr[i]) {
				int index = st.pop();
				answer[index] = arr[i];
			}
			
			st.push(i);
			
		}
		while(!st.isEmpty()) {
			answer[st.pop()] = -1 ;
		}
		StringBuilder sb = new StringBuilder();
		for(int num : answer) {
			sb.append(num+ " ");
		}
		
		System.out.println(sb.toString());
	}

}