[백준 2493번] 탑 - JAVA

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

2493번: 탑

풀이

사용한 알고리즘 : 스택

 

풀이전략

 

1. 탑의 높이 입력이 들어올 때마다

입력 값이 stack의 top에 저장된 값보다 크면, 기존 stack에서 top 원소가 더 큰게 있을 때까지 pop하고

입력 값이 stack의 top에 저장된 값보다 작으면, stack의 top 인덱스를 resut에 저장하고 기존 stack의 원소들을 유지한다.

2. stack에 현재 입력값을 push 하고 1번 과정을 스택이 빌 때까지 반복한다.

3. result를 출력한다.

 

 

 

제출코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    static class Top{
        int index;
        int height;

        Top(int index,int height){
            this.index=index;
            this.height=height;
        }

        public int getIndex() {
            return index;
        }

        public int getHeight() {
            return height;
        }
    }
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N=Integer.parseInt(br.readLine());
        Stack<Top> stack = new Stack<>();
        st=new StringTokenizer(br.readLine());
        int result[] = new int[N];
        stack.push(new Top(0,Integer.parseInt(st.nextToken())));
        result[0]=0;
        for(int i=1;i<N;++i){
            Top temp=new Top(i,Integer.parseInt(st.nextToken()));
            while(!stack.isEmpty()){
                if(stack.peek().getHeight()<temp.getHeight()){
                    stack.pop();
                }
                else{
                    result[temp.getIndex()]=stack.peek().getIndex()+1;
                    break;
                }
            }
            stack.push(temp);
        }

        for(int i=0;i<N;++i){
            System.out.print(result[i]+" ");
        }
    }
}