문제

입력

출력

예제

idea

정리

1. 입력받은 값들을 배열에 넣는다.
2. 뒤에서부터 값을 비교하며 벽에 팅길시 그 위치를 대입하고 아직 팅기지 않는다면 스택에 넣는다
3. 벽을 한칸씩 진행시키며 비교한다.
   (여기부터 수도코드에서 부족했던 추가 구현)
4. 스택을 한개를 더 만들어 자리값을 저장하여 스택에서 빠져나갈때 자리를 알 수 있도록 한다.
5. 스택은 정렬되어 들어가게 되는 구조이기 때문에 벽과 비교를 할 때 그 벽보다 큰 스택값이 있다면 이후 스택은 계산을 하지 않아도 된다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
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));
	      StringTokenizer st = new StringTokenizer(br.readLine());
	      Stack<Integer> stack= new Stack<>();
	      Stack<Integer> stack_2= new Stack<>();
	      StringBuilder sb = new StringBuilder();
	      int k=0;
	      int N = Integer.parseInt(st.nextToken());
	    
	      int top[]= new int[N];
	      st = new StringTokenizer(br.readLine());
	      
	      for(int i=0;i<N;i++)
	    	top[i]= Integer.parseInt(st.nextToken());
	        
	     for(int i=N-1;i>=-1;i--) {
	    	 if(i==-1)
	    	 {
	    		 k=stack.size();
	    		 for (int j = 0; j < k; j++) {
					top[stack_2.peek()]=0;
					stack_2.pop();
							
				}
	    		 break;
	    	 }
	    	 if(stack.isEmpty()==true) {
	    		 stack.push(top[i]);
	    		 stack_2.push(i);
	    	 }
	    	 else if(stack.peek()<=top[i]) {
	    		 k=stack.size();
	    		 for(int j=1;j<=k;j++) {
	    			 if(stack.peek()<=top[i]) {
	    				 top[stack_2.peek()]=i+1;
	    				 stack.pop();
	    				 stack_2.pop();
	    			 }
	    			 else {	    			
	    	    		 break;
	    			 }
	    		 }
	    		 stack.push(top[i]);
	    		 stack_2.push(i);
	    	 }
	    	 else {
	    		 stack.push(top[i]);	
	    		 stack_2.push(i);
	    	 }
	     }
	     for(int i=0;i<N;i++)
	    	 sb.append(top[i]).append(" ");
	     System.out.println(sb);
	}
}

결과