탑

백준 2493번 : 탑

알고리즘

초기화

1. 탑의 개수 N과 각 탑의 높이를 입력받는다.
2. 스택 초기화 스택에는 각 탑의 번호와 높이를 저장한다.

탐색

1. 스택이 비어있으면 0을 출력하고, i와 top을 stack 저장
2. 스택이 비어있지 않다면, 스택 맨 위의 값이랑 top을 비교후 맨 위 값이 더 크다면 (레이저를 쏠 수 있다면) 해당 값의 i를 출력한다. break로 pop 하지 않고 바로 push
3. 값이 더 크지 않다면 pop -> 레이저가 닿지 않음 pop 시켜서 그 앞에 값과 한번 더 비교 while 문을 사용한 이유. ->push

코드

package Gold_5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Top {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        Stack<int[]> stack = new Stack<>();

        // 백준 2493

        // 예제 입력: 6 9 5 7 4
        for(int i = 1; i <= n; i++) {
            int top = Integer.parseInt(st.nextToken()); // 현재 탑의 높이

            while(!stack.isEmpty()) {
                if(stack.peek()[1] >= top) { // 스택의 탑이 현재 탑보다 크거나 같으면
                    System.out.print(stack.peek()[0] + " "); // 신호를 수신할 수 있는 탑의 번호 출력
                    break;
                }
                stack.pop(); // 현재 탑보다 작은 탑들은 팝
            }

            if(stack.isEmpty()) {
                System.out.print("0 "); // 수신할 수 있는 탑이 없으면 0 출력
            }

            stack.push(new int[] {i, top}); // 현재 탑을 스택에 푸시
        }
    }
}

입력

5
6 9 5 7 4

동작 예시

첫 번째 탑 (i = 1, 높이 = 6)

• 스택이 비어 있으므로, 출력: 0
• 스택에 [1, 6]을 추가
• 스택 상태: [[1, 6]]

두 번째 탑 (i = 2, 높이 = 9)

• 스택의 탑 [1, 6]의 높이 6은 현재 탑 9보다 작으므로, 스택에서 팝
• 스택이 비어 있으므로, 출력: 0
• 스택에 [2, 9]을 추가
• 스택 상태: [[2, 9]]

세 번째 탑 (i = 3, 높이 = 5)

• 스택의 탑 [2, 9]의 높이 9는 현재 탑 5보다 크므로, 출력: 2
• 스택에 [3, 5]을 추가
• 스택 상태: [[2, 9], [3, 5]]

네 번째 탑 (i = 4, 높이 = 7)

• 스택의 탑 [3, 5]의 높이 5는 현재 탑 7보다 작으므로, 스택에서 팝
• 스택의 다음 탑 [2, 9]의 높이 9는 현재 탑 7보다 크므로, 출력: 2
• 스택에 [4, 7]을 추가
• 스택 상태: [[2, 9], [4, 7]]

다섯 번째 탑 (i = 5, 높이 = 4)

• 스택의 탑 [4, 7]의 높이 7은 현재 탑 4보다 크므로, 출력: 4
• 스택에 [5, 4]을 추가
• 스택 상태: [[2, 9], [4, 7], [5, 4]]

최종 출력

0 0 2 2 4