백준 - 탑 with JAVA

 

 

 

해당 문제는 간단하지만 사소한 모든 요소가 메모리 초과, 시간 초과에 영향을 끼칠 수 있어서 기록해두려고 한다.

 

 

1. 기본적으로 입력은 BufferedReader로 받고 빈칸을 두고 입력을 받는다면, StringTokenizer를 사용하자

2. Stack을 사용한다면 stack.isEmpty()를 통해 비어있는지 여부를 체크하자. 만약 size()>0을 한다면 비효율적이다.

3. Stack을 사용한다면 pop(), push()를 통해 넣었다 빼기를 반복하지말고 peek()를 무조건 쓰자

4. printf보단 print가 메모리 초과가 발생하지 않는다.

 

 

로직

- 새로운 입력을 받을 때, Stack의 후입선출 구조를 통해 현재 타워보다 높이가 큰 수가 나올때까지 확인한다.

- 확인 후 새로운 타워를 Stack에 넣는다.

 

예시 : 높이가 9, 6, 7, 8, 4라고 가정하자 8 타워를 체크할 때, 6, 7은 제거되고 스택에 8이 들어간다. 이 후, 4 타워는 8이 가장 가까우면서 4보다 높은 타워가 된다. 이 때, 4 입장에서 6, 7은 고려하지 않아도 된다.

 

 

 

코드 

public class Q2 {
    static class Tower{
        int height;
        int index;
        public Tower(int height, int index){
            this.height= height;
            this.index = index;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Tower> stack = new Stack<>();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++){
            int height = Integer.parseInt(st.nextToken());
            while(!stack.isEmpty()){
                Tower before = stack.peek();
                if(before.height > height){
                    System.out.print(before.index + " ");
                    break;
                }
                stack.pop();
            }
            if(stack.isEmpty()){
                System.out.print(0 + " ");
            }
            stack.push(new Tower(height, i+1));
        }
    }
}