BOJ - 2493 ) 탑

---

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

2493번: 탑

 

---

Stack 자료구조를 사용하여 현재까지의 탑의 높이를 저장하여 

 

내 왼쪽의 탑들중 신호를 수신하는 탑을 찾는 문제이다.

 

수신되는 탑을 찾기위하여 현재까지 저장된 높이가 내높이보다 크면 add연산을 진행하고

 

작다면 나보다 큰 높이가 나올때까지 poll연산을 진행한다.

---

package algorithm_2022;

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

public class boj_2439 {

	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
	    int n = Integer.parseInt(st.nextToken());
	    int arr[] = new int[n];
	    int index[] = new int[n];
	    Stack<int[]> s = new Stack<>();
	    st = new StringTokenizer(br.readLine());
	    for(int i=0;i<n;i++) {arr[i] = Integer.parseInt(st.nextToken());}
	    
	    for(int i=n-1;i>=0;i--) {
	    	if(s.isEmpty()) {
	    		s.add(new int[] {arr[i],i});
	    		continue;
	    	}
	    	
	    	if(s.peek()[0] > arr[i]) {
	    		s.add(new int[] {arr[i],i});
	    	} else {
	    	   while(s.peek()[0] < arr[i]) {
	    		   index[s.peek()[1]] = i+1;
	    		   s.pop();
	    		   if(s.isEmpty()) break;
	    	   }
	    	   s.add(new int[] {arr[i],i});
	    	}
	    }
	    StringBuilder sb = new StringBuilder();
	    for(int i=0;i<n;i++) {
	      sb.append(index[i]+" ");	
	    } System.out.println(sb.toString());

    }

}

---