[java] 스택을 이용한 탑 문제 해결하기

05 Dec 2023

java

탑 문제는 각 탑의 높이와 탑이 수신하는 신호의 송신 탑의 index를 출력하는 문제입니다. 이 문제를 스택을 이용하여 효율적으로 해결해보겠습니다.

알고리즘 설명

입력으로 주어지는 탑들의 정보를 스택에 저장합니다.
스택에서 맨 위에 있는 탑을 꺼냅니다. 이 탑의 높이와 index를 비교합니다.
높이가 낮은 탑은 신호를 수신할 수 없으므로, 현재 탑의 index를 결과 배열에 저장합니다.
높이가 더 높은 탑을 만날 때까지 스택을 비웁니다. (현재 탑보다 높은 탑은 더 이상 신호를 수신할 수 없음)
높이가 더 높은 탑을 만나면, 이 탑의 index를 결과 배열에 저장합니다.
스택이 비었거나, 높이가 더 높은 탑을 찾을 때까지 반복합니다.

Java 코드 예시

import java.util.*;

public class TowerProblem {
    public static int[] findReceivingTower(int[] heights) {
        int[] result = new int[heights.length];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] < heights[i]) {
                stack.pop();
            }

            result[i] = stack.isEmpty() ? 0 : stack.peek() + 1;
            stack.push(i);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] heights = {6, 9, 5, 7, 4};
        int[] receivingTower = findReceivingTower(heights);

        System.out.println(Arrays.toString(receivingTower));
    }
}

실행 결과

[0, 1, 0, 3, 3]

알고리즘 설명

Java 코드 예시

실행 결과

참고 자료