kingsubin

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

public class boj_2493 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static Stack<Razer> waiting = new Stack<>();
    static Stack<Razer> pending = new Stack<>();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        st = new StringTokenizer(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();

        // 스택에 반대로 쌓기
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = n; i > 0; i--) {
            waiting.push(new Razer(arr[i], i));
        }

        // 초기값
        pending.push(waiting.pop());
        list.add(0);

        while (!waiting.isEmpty()) {

            if (waiting.peek().height > pending.peek().height) { // 레이저가 닿지 못하는 경우
                while (!pending.isEmpty() && (pending.peek().height < waiting.peek().height)) { 
                    pending.pop(); // 닿을때까지 작은놈은 무시
                }

                if (pending.isEmpty()) { // 끝까지 못 찾음
                    list.add(0);
                } else { // 어딘가에 닿았음
                    list.add(pending.peek().index);
                }
            } else { // 레이저가 바로 닿음
                list.add(pending.peek().index);
            }

            pending.push(waiting.pop());
        }

        // 출력
        for (Integer i : list) {
            bw.append(i + " ");
        }
        bw.flush();
        bw.close();
    }
}

class Razer {
    int height;
    int index;

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

(1) 나의 풀이

 

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

public class boj_2493 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        Stack<Top> s = new Stack<>();

        for (int i = 1; i <= N; i++) {
            int h = Integer.parseInt(st.nextToken());

            if (s.isEmpty()) {
                sb.append("0 ");
                s.push(new Top(h, i));
            } else {
                while (true) {
                    if (s.isEmpty()) {
                        sb.append("0 ");
                        s.push(new Top(h, i));
                        break;
                    }

                    Top top = s.peek();
                    if (top.height > h) {
                        sb.append(top.index + " ");
                        s.push(new Top(h, i));
                        break;
                    } else {
                        s.pop();
                    }
                }
            }
        }

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

class Top {
    int height;
    int index;

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

(2) 다른 풀이

굳이 뒤로 할 필요없이 앞에서부터 이렇게 할 수 있었음

생각이 안났다 ...

 

 

생각

- n의 범위가 크니까 for문으로 도는건 시간초과 -> 다른 자료구조 사용, 생각하다 보니까 스택을 

  뒤에서부터 넣는다면 맨 앞 탑에서부터의 레이저가 닿는 곳을 구하기 좋을거같다고 생각

  근데 출력할때는 index의 값이 필요하니 따로 class를 만들어서 스택에 담음

  탐색하다가 만약 나보다 낮은 탑을 만나면 이건 제거해도 상관이없음 

  왜냐면 현재 탑의 높이가 더 높기때문에 다음 탑에서 레이저를 발사해도 걸리는건 현재의 탑임 

  이런식으로 레이저가 탑에 걸리던가 pending stack이 빌때까지 pop해준다.

 

- emptystack 에러때문에 계속 걸렸는데 해결했음.

   while문 사용하는게 아직도 머리가 빨리 안돌아간다 ...

- 뭔가 더 다듬을 수 있을거 같은데 ...