[Baekjoon] 2493번: 탑 - Java

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

2493번: 탑

문제 설명

문제가 조금 장황한 것 같지만 핵심은 간단하다. 주어진 탑들이 마지막부터 반대 방향으로 레이저를 발사하는데 자신보다 높은 탑만 신호를 받을 수 있다. 즉, 마지막부터 자신보다 높은 가장 가까운 탑을 찾아내면 되는 것이다. 사이트 예제를 그림으로 설명하면 다음과 같다.

이는 스택을 활용하면 효율적으로 해결할 수 있다. 오등큰수와 비슷한 문제이다.

풀이 방법

핵심 로직은 다음과 같다. 중요한 점은 스택에 탑의 인덱스를 넣는다는 것이다.

for (int i = towers.length - 1; i >= 0; i--) {
    while (!stack.isEmpty() && towers[stack.peek()] < towers[i]) {
        answer[stack.pop()] = i + 1;
    }
    stack.push(i);
}

마지막부터 거꾸로 찾아가야 하므로 마지막 탑의 인덱스부터 스택에 넣는다. 만약 푸시할 탑이 스택의 맨 위에 있는 탑보다 더 높은 탑인 경우 현재 스택에 들어있는 탑을 빼고 정답 배열에 푸시할 탑의 인덱스 + 1한 값을 넣는다.

전체 코드는 다음과 같다.

package baekjoon.stack;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Stack;

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

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

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int N = Integer.parseInt(br.readLine());
            int[] towers =
                    Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int[] answer = new int[N];

            for (int i = towers.length - 1; i >= 0; i--) {
                while (!stack.isEmpty() && towers[stack.peek()] < towers[i]) {
                    answer[stack.pop()] = i + 1;
                }
                stack.push(i);
            }

            Arrays.stream(answer).forEach(receiveTower -> wrap(() -> bw.write(receiveTower + " ")));

            bw.flush();
        }
    }

    @FunctionalInterface
    public interface IOExceptionConsumer {
        void accept() throws IOException;
    }

    public static void wrap(IOExceptionConsumer target) {
        try {
            target.accept();
        } catch (IOException e) {
            throw new RuntimeException();
        }
    }
}