탑

첫번째 풀이(실패)

스택을 세 개 선언한다. origin에 입력되는 탑들을 저장한다.
origin.pop()으로 마지막 탑을 뽑고, 그 다음 탑의 높이를 peek() 해서 비교하고 pop()한 탑의 높이보다 낮을 경우에는 temp 스택으로 push, 높을 경우에는 해당 탑의 인덱스를 result 스택에 저장한다. result에 값을 저장하게 되면, temp의 값들을 다시 pop()해서 origin으로 넣어준다.
위 과정을 origin에 저장된 값들이 전부 비워질때까지 반복한다.

이 풀이는 분기가 좀 까다로워서 코드를 못짜기도 했고, 계산해보니 시간초과가 날 거 같아서 다른 풀이를 생각해보기로했다.

두번째 풀이(성공)

도저히 방법이 안떠올라서 다른 사람들의 풀이를 보고 코드를 작성했다.
탑의 개수만큼 반복문을 돈다.
처음에 스택이 비어있을 경우 0을 stringBuilder에 append한다.
비어있지 않다면 while 반복문을 돌면서 스택의 제일 위에 값을 peek해서 현재 저장하려는 탑과 높이를 비교하고 peek한 값이 더 크다면 해당 탑의 인덱스를 stringBuilder에 append하고 더 작다면 이후에도 비교할 필요가 없으니 pop해준다.

package BOJ;

import java.io.*;
import java.util.*;

public class sol2493 {
    static int N;
    static Stack<Struct> origin = new Stack<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int height = Integer.parseInt(st.nextToken());
            if (origin.isEmpty()) {
                sb.append("0 ");
                origin.push(new Struct(height, i + 1));
            } else {
                while (true) {
                    if (origin.isEmpty()) {
                        sb.append("0 ");
                        origin.push(new Struct(height, i + 1));
                        break;
                    }
                    Struct s = origin.peek();
                    if (s.height > height) {
                        sb.append(s.index).append(" ");
                        origin.push((new Struct(height, i + 1)));
                        break;
                    } else {
                        origin.pop();
                    }
                }
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static class Struct {
        int height;
        int index;

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