[정올] 1809 : 탑

문제 >> 1809 : 탑

- 탑의 정보를 담는 클래스 Tower. 탑의 번호(number)와 높이(size)를 저장.

- 최종 출력할 답을 담을 list

- 입력 순서대로 스택에 넣어준다.

- 이 때 스택이 비어있다면, 현재 탑의 레이저를 수신할 수 있는 장치는 없다. ==> list에 0을 넣어준다. list.add(0)

- 스택이 비어있지 않다면 ..

  가장 위에 담아있는 tower의 정보를 peek 한다.

  만약 peek 한 tower의 size가 현재 탑보다 작다면, pop한다. (현재 tower의 높이가 더 높기 때문에, 앞으로 어떤 탑의 레이저도 수신할 수 없다.

  현재 탑의 size보다 큰(즉, 현재 탑의 레이저를 수신할 수 있는) tower가 나올때까지 pop을 반복한다.

  현재 탑의 size보다 큰 tower를 만나면, 그 tower의 number를 list에 add 해주고, 현재 탑을 push 해준다.

  만약 pop을 반복하다 스택이 비면, 현재 탑의 레이저를 수신할 수 있는 탑이 없다는 뜻이므로, list에 0을 add해주고 현재 탑을 스택에 push한다.

- 최종 list를 출력한다.

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
 
class Tower {
    int number;
    int size;
     
    public Tower(int number, int size) {
        this.number = number;
        this.size = size;
    }
}
 
public class Main {
    public static void main(String[] args) {
         
        Scanner sc = new Scanner(System.in);
         
        //int T = sc.nextInt();
         
        //for(int t=1;t<=T;t++) {
            Stack<Tower> stack = new Stack<>();
            ArrayList<Integer> list = new ArrayList<>();
            int N= sc.nextInt();// 탑의 수
            int now=0; // 탑의 높이
            int idx=0;
            //int[] ans = new int[N]; //answer
            for(int i=0;i<N;i++) {
                 
                now = sc.nextInt();
                 
                if(stack.empty()) list.add(0); // 스택이 비어있으면 앞에 건물이 현재건물now보다 낮은 건물이거나 처음으로 넣는 건물
                else {
                    while(!stack.empty()) {
                         
                         
                        if(stack.peek().size < now ) { // 스택에 있는 건물이 지금 넣으려는 건물보다 낮으면  pop
                            stack.pop();
                            if(stack.empty()) list.add(0); // 낮은 건물은 계속 pop하다가 스택이 비어 있으면 리스트에 0을 추가
                             
                        } else {
                            list.add(stack.peek().number); // 스택에 있는 건물이 지금 넣으려는 건물보다 높으면 그 값을 list에 추가
                            break;
                        }
                    }
                }
                stack.push(new Tower(++idx,now));
            }
             
            //System.out.print("#"+" ");
            for(int i=0;i<list.size();i++) {
                System.out.print(list.get(i)+" ");
            }
            System.out.println();
        //}
    }
}