[BOJ] 2493. 탑 (🥇, 스택)

🔗

풀이

⚠️ 문제 요약

탑에서 왼쪽 방향으로 레이저를 쐈을 때 수신하게 되는 탑의 높이를 찾는 문제. 레이저를 쏜 탑의 높이보다 높은 높이를 갖는 탑만 수신할 수 있다.

💡 아이디어

현재 탑의 위치보다 높은 위치의 탑 위치를 찾는 문제이다. 왼쪽에서 오른쪽으로 하나씩 확인해나가면 된다. 전체 탑의 개수가 50만이기 때문에 각 탑에 대해서 매번 왼쪽을 일일이 탐색하면 시간초과남.

결국 현재 탑을 기준으로 왼쪽에 있는 탑들에 대한 정보를 어딘가에 저장해두고 저장된 정보를 유용하게 꺼낼 수 있는 자료구조가 필요하다. 현재 탑의 위치보다 높기만하면 되고 얼마나 더 높은지는 중요하지 않다. 왼쪽에 위치해 있으면서 어쨌든 높기만 하면 되기 때문에 현재 탑을 기준으로 왼쪽으로 하나씩 차례대로 볼 수 있으면 된다.

왼쪽에서 오른쪽으로 탐색하면서(저장), 값을 꺼내 확인할 때는 오른쪽에서 왼쪽으로 찾아야 하는 방식은 LIFO인 스택이 가장 적합하다.

모든 탑에 대해서 우선적으로 스택에서 자신보다 높은 탑의 위치를 찾는다. 가장 가까운 순서(오른쪽 -> 왼쪽)으로 탐색하게 되며 자신보다 낮은 탑은 스택에서 제거한다. 더 높은 위치의 탑을 찾게 되면 탐색을 중단하고, 탑의 위치를 기록한다. 이후 자신의 높이를 저장한다. 이 과정을 반복하게 된다.

코드를 더 간결하게 하기 위해서 stack.isEmpty() 를 쓰는 대신에 절대 꺼내지지 않을 값을 미리 저장했다. 왼쪽에 더 높은 높이의 탑이 없는 경우 0이 저장된다. 가장 높은 높이의 탑이 1억이기 때문에 1억보다 높은 높이의 탑을 미리 tower 배열의 가장 앞에 저장해놓고 스택에도 인덱스 0값을 미리 저장해서 스택이 비어있지 않을 수 있도록 했다.

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

public class Main {
    private static final int MAX_HEIGHT = 100_000_001;
    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());
        int[] tower = new int[n+1];
        tower[0] = MAX_HEIGHT;
        for (int i = 0; i < n; i++) {
            tower[i+1] = Integer.parseInt(st.nextToken());
        }

        // 스택 생성
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        // tower 배열 값 스택에 저장
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            int now_height = tower[i+1];
            while(tower[stack.peek()] < now_height) {
                stack.pop();
            }
            answer[i] = stack.peek();
            stack.push(i+1);
        }
        
        
        // 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(answer[i] + " ");
        }
        System.out.println(sb.toString());
    }
}