https://programmers.co.kr/learn/courses/30/lessons/42588?language=java

Tower.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Stack;

/**
 * 2020-06-14 by solar-beam
 * https://programmers.co.kr/learn/courses/30/lessons/42588?language=java
 * 스택/큐 연습문제, 신호는 왼쪽으로만 보낼 수 있다
 * */

public class Main {
    public static void main(String[] args) {
        int[] case1 = {6,9,5,7,4}; solution(case1);
        int[] case2 = {3,9,9,3,5,7,2}; solution(case2);
        int[] case3 = {1,5,3,6,7,6,5}; solution(case3);
    }

    public static int[] solution(int[] heights){
        int[] answer = new int[heights.length];

        //brute-force
        int bf_cnt1 = 0, bf_cnt2=0;
        for(int i=0; i<heights.length; i++){
            bf_cnt1++;
            for(int j=i; j>=0; j--){
                bf_cnt2++;
                if(heights[j]>heights[i]){
                    answer[i]=j+1;
                    break;
                }
            }
        }

        //스택에 담아놨다가 자신보다 큰 탑을 만나면 쏟아놓기
        // * 불변식 : 스택에는 연속하여 작아지는 값들만 입력한다.
        Stack<Integer> cheat = new Stack();
        int st_cnt1=0, st_cnt2=0, st_cnt3=0;
        for(int i = heights.length-1; i>0; i--){
            //스택이 비어있다
            //스택이 차있는데 PICK해보니 크거나 같다
            //스택이 차있는데 PICK해보니 작다
            st_cnt1++;
            while(!cheat.isEmpty()){
                st_cnt2++;
                if(heights[cheat.peek()]>=heights[i]) break;
                st_cnt3++;
                answer[cheat.peek()] = i+1;
                cheat.pop();
            }
            cheat.push(i);
        }

        //빠른스택 Deque : http://tcpschool.com/java/java_collectionFramework_stackQueue
        //직접구현 : https://donghoson.tistory.com/150
        MyStack cheat2 = new MyStack();
        int mst_cnt1=0, mst_cnt2=0, mst_cnt3=0;
        for(int i = heights.length-1; i>0; i--) {
            //스택이 비어있다
            //스택이 차있는데 PICK해보니 크거나 같다
            //스택이 차있는데 PICK해보니 작다
            mst_cnt1++;
            while (!cheat2.isEmpty()) {
                mst_cnt2++;
                if (heights[cheat2.peek()] >= heights[i]) break;
                mst_cnt3++;
                answer[cheat2.peek()] = i + 1;
                cheat2.pop();
            }
            cheat2.push(i);
        }
        //질문
        // 큐 검색시간(log M), 큐 구현시간(n log N), 정렬된 자료구조
        // 힙과 스택은 왜 다른가

        //print
        //for(int i=0; i<answer.length; i++) System.out.print(answer[i]+" ");
        //System.out.println();

        System.out.println("brute force : 외부for("+bf_cnt1+"), 내부for("+bf_cnt2+")");
        System.out.println("stack STL : for("+st_cnt1+"), while("+st_cnt2+"), while 內 if 이하("+st_cnt3+")");
        System.out.println("stack my own : for("+mst_cnt1+"), while("+mst_cnt2+"), while 內 if 이하("+mst_cnt3+")");

        return answer;
    }

    private static class MyStack {
        int[] data;
        int pos;
        int size;

        MyStack(){
            data = new int[1000];
            pos = -1;
            size = 1000;
        }
        MyStack(int stack_size){
            data = new int[stack_size];
            pos = -1;
            size = stack_size;
        }

        boolean isEmpty(){
            return pos<0;
        }

        int peek(){
            if(isEmpty()) return -1;
            return data[pos];
        }

        int pop(){
            if(isEmpty()) return -1;
            return data[pos--];
        }

        int push(int e){
            if(pos+1<size) data[++pos] = e;
            return e;
        }
    }
}

brute-force

테스트 1 〉 | 통과 (1.59ms, 50.2MB)
테스트 2 〉 | 통과 (1.49ms, 52.6MB)
테스트 3 〉 | 통과 (1.58ms, 50.3MB)
테스트 4 〉 | 통과 (1.43ms, 52.7MB)
테스트 5 〉 | 통과 (1.58ms, 52.9MB)
테스트 6 〉 | 통과 (1.41ms, 53.4MB)
테스트 7 〉 | 통과 (1.41ms, 51MB)
테스트 8 〉 | 통과 (1.41ms, 52.3MB)

with stack(arraylist)

테스트 1 〉 | 통과 (1.45ms, 54.5MB)
테스트 2 〉 | 실패 (2.83ms, 50.2MB)
테스트 3 〉 | 통과 (1.53ms, 52.4MB)
테스트 4 〉 | 실패 (2.89ms, 50MB)
테스트 5 〉 | 통과 (1.49ms, 50.4MB)
테스트 6 〉 | 실패 (3.24ms, 50.1MB)
테스트 7 〉 | 통과 (1.43ms, 51.9MB)
테스트 8 〉 | 통과 (1.40ms, 49.9MB)

with stack, arraydeque, mystack

테스트 1 〉 | 통과 (1.51ms, 52.7MB)
테스트 2 〉 | 실패 (2.74ms, 52.3MB)
테스트 3 〉 | 통과 (1.53ms, 52.6MB)
테스트 4 〉 | 실패 (2.88ms, 50.7MB)
테스트 5 〉 | 통과 (1.74ms, 52.9MB)
테스트 6 〉 | 실패 (2.88ms, 52.8MB)
테스트 7 〉 | 통과 (1.54ms, 54.4MB)
테스트 8 〉 | 통과 (1.54ms, 52.5MB)

#1
brute force : 외부for(5), 내부for(10)
stack STL : for(4), while(4), while 內 if 이하(3)
stack my own : for(4), while(4), while 內 if 이하(3)

#2
brute force : 외부for(7), 내부for(17)
stack STL : for(6), while(7), while 內 if 이하(4)
stack my own : for(6), while(7), while 內 if 이하(4)

#3
brute force : 외부for(7), 내부for(18)
stack STL : for(6), while(6), while 內 if 이하(3)
stack my own : for(6), while(6), while 內 if 이하(3)