[백준] 17298번 오큰수 (java, 스택)

www.acmicpc.net/problem/17298

17298번: 오큰수

O(n)시간으로 현재 위치 수보다 더 큰 수를 찾는 문제

 

스택으로 푸는 걸 알고있어서 구현은 금방했는데도 시간 초과가 나서 헤맸다.

배열을 모두 출력할 때 모두 system.out을 쓰기보다 Stringbuilder로 문자열로 만든 다음에 한 번 출력해야 시간초과가

나지 않는다.

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

public class Main {
	static int n;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		Stack<Integer> st=new Stack<>();
		int[] arr=new int[n];
		String[] s=br.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			arr[i]=Integer.parseInt(s[i]);
		}
		for (int i = 0; i < n; i++) {
			while(!st.isEmpty() && arr[st.peek()]<arr[i]) {
				arr[st.pop()]=arr[i];
			}
			st.push(i);
			
		}
		while(!st.isEmpty()) {
			arr[st.pop()]=-1;
		}
		StringBuilder sb=new StringBuilder();
		for (int i = 0; i < n; i++) {
			sb.append(arr[i]+" ");
		}
		System.out.println(sb.toString());
		
		
	}
}

 

---

첫 풀이

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

public class Main {
	static int n;
	public static void main(String[] args)  {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		Stack<Integer[]> st=new Stack<>();
		int[] arr=new int[n];
		Arrays.fill(arr, -1);
		for (int i = 0; i < n; i++) {
			int cur=sc.nextInt();
			while(!st.isEmpty() && st.peek()[0]<cur) {
				arr[st.pop()[1]]=cur;
			}
			st.add(new Integer[] {cur,i});
			
		}
		
		StringBuilder sb=new StringBuilder();
		for (int i = 0; i < n; i++) {
			sb.append(arr[i]+" ");
		}
		System.out.println(sb.toString());
		
		
	}
}