2493 탑

 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       Stack<int[]> st = new Stack();
        int arr[] = new int[2];
        StringTokenizer str = new StringTokenizer(br.readLine(), " ");
        StringTokenizer str2 = new StringTokenizer(br.readLine(), " ");    
        int N = Integer.parseInt(str.nextToken());
        for(int i = 0; i < N; i++) {
            arr[1] =  Integer.parseInt(str2.nextToken());
            while(true) {
                if(st.empty()) {
                    System.out.print(0 + " ");
                    break;
                }
                if(st.peek()[1] > arr[1]) {
                    System.out.print(st.peek()[0]+ " ");
                    break;
                }
                else
                    st.pop();
            }
 
            st.push(new int[] {(i+1),arr[1]});
        }
    }
}
 

메모리와 시간을 줄여주는게 중점인 문제.

stack을 활용한다는 것을 떠올린다면 매우 쉬워지는 문제다.

자신보다 작은 값이라면 pop을 해주고 자신보다 큰값으면 그값에 해당하는 인덱스를 출력하고 

자기자신을 push하면 된다.

 

맨처음에는 string을 활용해서 풀어보려했지만 연산이 너무 많아지는 관계로 포기했다.

그리고 스텍을 사용했는데,

여기서 메모리초과가 많이나는 경우는 자바의 경우 Scanner가 무지하게 메모리를 잡아먹기 때문인것 같다.

버퍼리더를 사용한다면 효과적으로 풀 수 있다고 생각한다.