[BoJ] - 2493번 탑

 

 

입력

• 첫 줄: 탑의 개수 N N N (1 ≤ N N N ≤ 500,000)
• 둘째 줄: N N N개의 탑 높이 (1 ≤ 높이 ≤ 100,000,000), 공백으로 구분
• 높이는 모두 서로 다름 (문제 조건)

출력

• 각 탑에서 발사된 레이저를 수신한 탑의 번호를 공백으로 구분해 출력
• 수신 탑이 없으면 0

 

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

 

 

해결 아이디어

---

이 문제는 스택을 사용하면 효율적으로 해결할 수 있습니다. 스택을 사용하기전 단순하게 접근을 했을떄, 직관적인 해결법은 왼쪽으로 모든 이전 탑을 확인하며, 자신보다 높은 첫 번째 탑을 찾는 것입니다. 

 

• 예: 5번 탑(높이 4)의 경우, 4번(7), 3번(5), 2번(9), 1번(6)을 순서대로 확인.
• 4번 탑(높이 7)이 높이 4보다 크므로 여기서 수신.

 

위 내용이 이해가 되셨다면 이 문제가 왜 완전 탐색이 비효율적인지 알아봅시다 

 

• N=500,000 N = 500,000 N=500,000일 때, 500,000×500,000≈250,000,000,000 500,000 \ times 500,000 \approx 250,000,000,000 500,000×500,000≈250,000,000,000 연산.
• 이는 일반적인 시간 제한(1~2초) 내에 처리하기 어렵습니다. 즉 따라서 더 효율적인 방법을 찾아야 합니다.

완전탐색이 비효율적인것은 확인했습니다. 그렇다면 스택은 왜 적합할까요 ? 문제 분석을 정확히 했다면 우리는 이전 탑들 중 더 높은 탑만 유지하면 됩니다. 스택은 가장 최근의 데이터를 빠르게 접근하고, 불필요한 데이터를 제거하는 데 최적입니다.

 

 

• 스택에 탑의 높이와 인덱스를 저장.
• 새 탑을 처리할 때, 스택의 top 탑이 현재 탑보다 낮으면 pop (이 탑은 더 이상 필요 없음).
• 스택의 top 탑이 현재 탑의 레이저를 수신.
• 현재 탑을 스택에 push.

이 패턴을 이해했을경우 왜 낮은 탑을 스택에서 제거하나? 라고 질문이 나올수있습니다. 만약 스택의 top 탑이 현재 탑보다 낮다면, 이후 탑들의 레이저는 현재 탑에서 먼저 수신되거나, 더 높은 탑을 찾을 것이므로 그 탑은 더 이상 필요 없습니다.

• 예: 높이 [6, 9, 5]에서, 3번 탑(높이 5)을 처리할 때 2번 탑(높이 9)이 스택에 있으면 1번 탑(높이 6)은 제거됨. 이유는 2번 탑이 더 가까우면서도 높기 때문입니다.

시간 복잡도는 최대 한번 push 되고 최대 한 번.pop 됩니다. 따라서 O(N) 압나다

 

코드를 보시면 아시겠지만 레이저는 왼쪽 방향으로 나아가는데 왜 정방향으로 탐색하나? 라고 생각될수있습니다. 

문제는 탑을 왼쪽부터 오른쪽으로 번호를 매기고, 레이저도 왼쪽으로 발사됩니다. 정방향(1번 탑부터)으로 탐색하면, 스택에 이전 탑들을 순서대로 쌓고, 필요 없는 탑을 제거하며 자연스럽게 수신 탑을 찾을 수 있습니다. 역순 탐색도 가능하지만, 정방향이 문제의 흐름과 더 직관적이고 가독성이 좋습니다. 

 

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

public class Main {
    static BufferedReader br;
    static int[] towerHeights;

    static class Tower {
        int index;
        int height;

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

    }

    static void input() {
        try {
            // 배포용 표준 입력
            br = new BufferedReader(new InputStreamReader(System.in));

            int n = Integer.parseInt(br.readLine().trim());

            towerHeights = new int[n];

            StringTokenizer st = new StringTokenizer(br.readLine().trim());

            for (int i = 0; i < n; i++) {
                int height = Integer.parseInt(st.nextToken());
                towerHeights[i] = height;
            }
        } catch (IOException e) {
            System.err.println("입력 오류: " + e.getMessage());
        }
    }

    static int[] solve() {
        int n = towerHeights.length;

        int[] receivers = new int[n];

        Stack<Tower> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            // 현재 탑보다 높이가 낮은 탑은 스택에서 제거
            while (!stack.isEmpty() && stack.peek().height <= towerHeights[i]) {
                stack.pop();
            }
            // 스택이 비어 있으면 수신 탑 없음(0), 아니면 스택의 top 탑이 수신 탑
            receivers[i] = stack.isEmpty() ? 0 : stack.peek().index;
            // 현재 탑을 스택에 추가 (1-based 인덱스)
            stack.push(new Tower(i + 1, towerHeights[i]));
        }

        return receivers;
    }

    public static void main(String[] args) {
        input();
        int[] receivers = solve();
        // StringBuilder로 출력 최적화
        StringBuilder sb = new StringBuilder();
        for (int receiver : receivers) {
            sb.append(receiver).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}