[알고리즘/자바] 백준 17298번 - 오큰수

 

17298번: 오큰수

 

시간초과로 상당히 고생한 문제.

 

처음 내가 풀었던 방식은 아래와 같다. 3이 있으면 우측으로 쭉 읽으면서 3보다 큰수가 나오면 break를 걸도록했다. 이렇게 하면 2중 for loop를 사용하게 되는데 worst case의 경우 n!이 나온다. 따라서 이렇게 풀면 당연히 시간초과.

 

결국 풀다가 백준님 강의를 듣고 아래의 소스코드로 정답을 맞췄다. 

 

해당 문제를 시간내 통과하기 위해서 Stack을 사용했다.

 

3 5 2 7이라는 숫자가 있다면 먼저 0(숫자3의 인덱스)을 Stack에 넣고 시작한다. (1) 주석

그리고 나머지 숫자 5 2 7을 하나씩 읽는다. (2) 주석

Stack이 비어있지 않고, 5가 Stack의 Top인덱스의 값보다 클 경우...  top에 있던 Index를 제거하고 정답지(ans)에 기록한다. (3)주석

이 후 5의 인덱스인 1을 Stack에 push한다. (4)주석

 

위 과정을 거치면 ans에 오큰수를 다 채울수 있다. 다만 오큰수가 없는 숫자의 인덱스는 그대로 Stack에 남아있으므로 해당 인덱스를 -1로 ans에 기록해줘야한다. (5) 주석

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws IOException{
		
		// 입출력
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); 
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Stack<Integer> stack = new Stack<Integer>();
		
		
		bf.readLine();
		String t2 =bf.readLine();
		String[] n = t2.split(" ");
		int ans[] = new int[n.length];
		
		stack.push(0); // (1)
		
		for(int i=1; i<n.length; i++) { // (2)
			
			if(stack.empty()) stack.push(i);
			
			//(3)
			while(!stack.empty() && Integer.valueOf(n[stack.peek()]) < Integer.valueOf(n[i])) {
				ans[stack.peek()] = Integer.valueOf(n[i]);
				stack.pop();
			}
			stack.push(i); //(4)
		}
		
        //(5)
		while(!stack.empty()) {
			ans[stack.peek()] = -1;
			stack.pop();
		}
		
		// (6)
		for(int i=0; i<ans.length; i++) {
			bw.write(ans[i] + " ");
		}
		bw.write("\n");
		
		
		////////////출력 이렇게 작성하면 시간초과!!!//////////////
		//String answer = "";
		//for(int i=0; i<ans.length; i++) {
		//	int oks = ans[i];
		//	if(oks == 0 ) oks = -1;
		//	answer += oks + " ";
		//}
		//bw.write(answer.substring(0,answer.length()-1));
		///////////////////////////////////////////////
		
		
		bw.flush();
		bw.close();
	}
		
}

 

위 소스에서 출력부분과 관련해서 한가지 주의할 점이 있는데 최대한 정답과 맞추기 위해서 제일 뒤의 공백을 제거하기 위한 작업을 수행했는데 시간 초과가 났다. ( 소스코드 가장 아래 주석 ) 

 

만약 로직이 n^2이나 n!이 아닌데 시간초과가 난다면 출력부분을 바꿔보도록 하자.