[JAVA/스택] 백준 2493 탑

1. 문제

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

2493번: 탑

 

2. 풀이

오른쪽에서 레이저를 쏘기 때문에 오른쪽으로 시작 할 수 있지만, 그렇게 하면 최악의 경우 N!의 복잡도가 발생할 수 있다. 따라서, stack을 활용해 오른쪽부터 계산한다. 풀이 과정은 아래와 같다.

• 탑의 위치와 높이를 스택에 모두 저장하기 위해 별도의 클래스를 만든다.
• 탑의 왼쪽부터 시작한다.
• while문을 이용해 stack에 있는 탑들을 돌아보며,
  • 현재의 탑 높이가 스택의 가장 위에 있는 탑의 높이보다 같거나 작은 경우(= 현재 탑에서 쏜 레이저가 해당 탑에 맞을 수 있는 경우), 스택의 가장 위에 있는 탑의 위치를 답에 추가한다(sb.append())
  • 탑들을 돌 때, 해당 현재 탑의 높이가 스택 가장 위에 있는 탑의 높이보다 큰 경우, 레이저를 수신할 수 없으므로 pop 한다.
• 스택이 비면, 레이저를 수신할 수 없으므로 0을 답에 추가한다.
• 해당 탑을 스택에 추가한다.

 

3. 코드

 

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

class top{
    int pos; // 위치
    int height; // 높이
    
    public top(int pos, int height) {
        this.pos = pos;
        this.height = height;
    }
}

public class Main {
    
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        
        String[] input = br.readLine().split(" ");
        Stack<top> s = new Stack<top>();
        
        for(int i = 1; i <= n; i++) {
            int nowH = Integer.parseInt(input[i-1]); // 현재 탑 높이
            
            while(!s.isEmpty()) {
                // 해당 탑 높이가 스택에 가장 위에 있는 탑의 높이보다 같거나 작은 경우
                if(s.peek().height >= nowH) {
                    sb.append(s.peek().pos + " "); // 해당 탑의 위치를 sb에 추가
                    break;
                }
                
                // 해당 탑 높이가 스택 가장 위에 있는 탑의 높이보다 큰 경우
                s.pop();
            }
            
            if(s.isEmpty()) {
                sb.append(0 + " "); // 레이저 못 맞음. 0을 sb에 추가
            }
            
            // 해당 탑 스택에 추가
            s.push(new top(i, nowH));
        }
        
        System.out.println(sb.toString());
    }
}