[백준] 17298번 : 오큰수(JAVA)

https://www.acmicpc.net/problem/17298

17298번: 오큰수

풀이

이중 포문(O(n2))으로 해결할려고하면 시간초과가 나옵니다.

알고리즘 분류에 스택이라고 있으니 스택으로 함 풀어봅시다.

먼저 입력받은 크기만큼 배열에 수를 입력받습니다.

 

스택이 비어있지 않고, 스택에 저장된 숫자의 배열 위치가 현재 체크하고자 하는 배열 위치보다 작으면, 그 배열 위치에 체크하고자 하는 배열위치의 값을 넣어주는 방식을 반복해줍니다.

스택에 수를 넣어주면서

 

그러다 1부터 size까지 다 돌았는데도 스택에 수가 있으면 우측에 큰 수가 없는 것이므로 stack에 값을 꺼내주면서 그 위치에 -1을 넣어주면 됩니다.

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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 size = Integer.parseInt(br.readLine());
		
		int[] num = new int[size];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < size; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		
		Stack<Integer> stack = new Stack<>();
		for(int i = 0; i < size; i++) {
			while(!stack.isEmpty() && num[stack.peek()] < num[i]) {
				num[stack.pop()] = num[i];
			}
			stack.add(i);
		}
		
		while(!stack.isEmpty()) {
			num[stack.pop()] = -1;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int n : num) {
			sb.append(n).append(" ");
		}
		System.out.print(sb);
	}
}