탑

📍 문제 설명

 

💡 접근

효율성을 위해 스택을 이용하여 풀어야하는 문제

1.현재 값과 스택의 값을 비교하여 현재 값이 더 크면 이전 지점의 스택의 값들을 계속해서 빼준다.

- 작은 이전 지점의 탑은 현재 지점의 탑에서 신호가 막히므로

2.신호 가능 지점을 발견했을땐 출력만 하고 멈춘다.

3.현재 지점의 탑을 스택에 넣는다.

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n;
    static int[] board;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        board = new int[n];
        for(int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }

        T.solution();
        System.out.println(sb);
    }

    private void solution() {
        Stack<Top> s = new Stack<Top>();

        for(int i = 0; i < n; i++) {
            //현재 값이 스택의 값보다 작거나 같아지는 부분 or 스택이 비어있지 않을 때까지 탐색
            while(!s.isEmpty()){
                //현재 값이 더 크면 빼주기
                if(board[i] >= s.peek().height) s.pop();
                //신호 가능지점 발견!
                else {
                    sb.append(s.peek().number + " ");
                    break;
                }
            }
            //신호보낼 수 있는 지점 없으면 0
            if(s.isEmpty()) sb.append(0 + " ");

            //현재 지점은 무조건 스택에 넣기
            s.push(new Top(board[i], i+1));
        }
    }

    private class Top {
        private int height;
        private int number;

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

        @Override
        public String toString() {
            return "Top{" +
                    "height=" + height +
                    ", number=" + number +
                    '}';
        }
    }
}