[ 백준 ] 2493 탑

📌 Problem

1 이상 1억 이하의 높이를 가지는 탑들이 좌우일렬로 세워져 있다. 각각의 탑들이 왼쪽으로 레이저를 송신하였을 때 이를 수신하는 탑의 번호를 출력하면 된다. 레이저 송신은 탑의 최대 높이에서만 가능하고 수신은 탑 전체에서 가능하다.

📌 Solution

Stack을 통해서 해결할 수 있는 문제이다. 맨 왼쪽 탑부터 차례대로 탐색하고 탐색을 완료한 탑은 Stack에 push한다. 맨 왼쪽 탑은 송신한 레이저를 수신할 수 있는 탑이 없기 때문에 0을 출력한다. 이후의 탑을 탐색할 때는 우선 Stack의 top을 확인하면서 현재 탑보다 작으면 pop한다. 현재 탑과 높이가 같거나 큰 탑이 나오면 해당 탑이 레이저를 수신하는 탑이다.

📌 Code

int TOWER_NUM = Integer.parseInt(reader.readLine());
Stack<Tower> towers = new Stack<>();
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
for (int t = 1; t <= TOWER_NUM; t++) {
    int height = Integer.parseInt(tokenizer.nextToken()), tno = 0;
    while (!towers.isEmpty()) {
        if (towers.peek().height >= height) {
            tno = towers.peek().tno;
            break;
        }
        towers.pop();
    }
    result.append(tno).append(' ');
    towers.push(new Tower(t, height));
}

static class Tower {
    int tno, height;

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