백준 17298 오큰수

골드 4 ㄷㄱㅈ ㄷㄱㅈ

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

오랫만에 올리는..코테문제..
다시 집중햇 문제를 풀도록 해야겠따..

스택 정복도전중..만난 4단계

앞으로 3걸음만 더가면 스택문제는 익숙해져서 잘풀것같다..

옥상정원 꾸미기 문제와 비슷하다 그러나 여기서는 몇번째가 아니라 값만 보여주면된다

즉 옥상정원처럼 그래프로 보면

이렇게 길이로 볼수잇고 오른쪽의 큰수이기때문에 맨 오른쪽부터 시작하면

4번째 값의 경우

3번째 값의 경우

2번째 값의 경우

1번째 값의 경우

잘 생각해보면 거꾸로 값을 집어넣을때마다 스택에 넣고관리를 해서 최신화를 해준다

엥 ? 그러면 문제같은 경우네는 2번쨰값의 경우까지돌면 결국 최신화된 .. 스택에는 5밖에 안남는데..

상관없다 왜냐하면 가장 오른쪽의 있는값이므로 가장 큰값이 아닌 본인값중 오른쪽에있는 값들중 가장 가까운 값을 찾는거기때문이다...

그리고 본인은 StringBuilder 앞에 넣는거를 잘못해서 String line 선언하고 + + + 연산하니까 시간초과가 펑!

그래서 그냥 배열에 담아주고 한번에 스트링빌더에 담고 println 해주었다..

그래서 코드는 다음과 같다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int count = Integer.parseInt(br.readLine());
		int bcount = count;
	      StringTokenizer st = new StringTokenizer(br.readLine());
	      StringBuilder sb = new StringBuilder();
	      Stack<Integer> s =new Stack<>();
	      Stack<Integer> bs = new Stack<>();
	      for(int i=0;i<count;i++) {
	    	  s.add(Integer.parseInt(st.nextToken()));
	      }
	      int[] answer = new int[count];
	      String line = "-1";
	      answer[--count] = -1;
	      bs.add(s.pop());
	      
	      
	      while(!s.isEmpty()) {
	    	  int now = s.pop();
	    	  boolean flag = false;
	    	  while(!bs.isEmpty()) {
	    		  int bnow = bs.peek();
	    		  
	    		  if(bnow<=now) {
	    			  bs.pop();
	    			  continue;
	    		  }
	    		  
	    		  answer[--count] = bnow;
	    		  flag = true;
	    		  break;
	    	  }
	    	  
	    	  if(!flag) answer[--count] = -1;
	    	  bs.add(now);
	      }
	      for(int i=0;i<bcount;i++) {
	    	  sb.append(answer[i]).append(" ");
	      }
	      System.out.println(sb);
	}

}