2493탑

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

초등학생들이 이런 문제를 푼단 말인가;;

비교적 쉽게 풀었다 휴... 50분정도 걸렸다

시간복잡도는 O(N) 이 아닐까...
최악의 경우라도 2N 이 되어서 상수 제거하면 N
레이저 N개가 다 충돌하는 경우가 최악의 경우라 볼 수 있다
N개의 타워에 N개가 충돌하는 거니까 2N 이라 생각해봄

public class Main {

    static class Razor implements Comparable<Razor>
    {
        int startpos;
        int height;

        public Razor(int startpos, int height) {
            this.startpos = startpos;
            this.height = height;
        }


        @Override
        public int compareTo(Razor o) {
            return this.height - o.height;
        }
    }


    public static void main(String[] args) {

        FastReader fr = new FastReader();

        int towerCnt = Integer.parseInt(fr.nextLine());

        //탑의 높이를 받아와~
        ArrayList<Integer> heightlist = new ArrayList<>();
        ArrayList<Integer> ret = new ArrayList<>();
        for(int i = 0; i < towerCnt; ++i)
        {
            heightlist.add(fr.nextInt());
            ret.add(-1);
        }


        //오른쪽에서 왼쪽으로 레이저를 쏠거야 쏠때마다 높이, 시작지점 저장. 최소힙을 사용해서. 오름차순으로 정렬한다
        PriorityQueue<Razor> qRazor = new PriorityQueue<>();
        for(int i = heightlist.size()-1; i >= 0; --i)
        {
            qRazor.add(new Razor(i, heightlist.get(i)));

            while(!qRazor.isEmpty())
            {
                if(qRazor.peek().height < heightlist.get(i))//작은타워부터 충돌하면 충돌지점을 ret에 저장
                {
                    Razor tmp = qRazor.poll();
                    ret.set(tmp.startpos, i);
                }
                else
                    break;

            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < ret.size(); ++i)
        {
            sb.append(ret.get(i) + 1);//인덱스 값 +1 보정

            if(i != ret.size()-1)
                sb.append(" ");
        }

        System.out.println(sb.toString());
    }

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next()
        {
            while(st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch(IOException e)
            {
                e.printStackTrace();
            }

            return str;
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }
    }
}