[Java] 백준 BOJ / 2493번: 탑

탑

문제

---

문제 설명

탑의 개수 N 과 이 탑들의 높이가 주어진다.

각 탑은 꼭대기에서 왼쪽으로 레이저 신호를 발사하는데 이 레이저 신호는 신호를 발사한 곳 보다 높은 탑에서만 수신할 수 있다고 한다.

이 때 각 탑에서 레이저 신호를 수신하는 탑들의 번호를 출력하는 프로그램이다.

---

구현

처음에는 입력을 다 받고 뒤에서부터 해야하나 싶었는데 도저히 생각이 안나서 다른 사람들의 풀이를 참고했다.

중요한 부분은 지금 나보다 왼쪽에 있는 탑들 중 현재의 탑 높이보다 높은 것 중 가장 오른쪽 탑을 찾아야 한다.

Stack 에 저장되는 값들은 지금까지 나온 높이가 클 수도 있는 탑들이 들어있을거고 새로 입력으로 들어오는 탑들을 보면서

1. 스택의 맨위에 있는 탑보다 높다면 그 탑은 현재 기준 다음에 나올 탑들에 영향을 줄 수 없기 때문에 pop으로 버리기

2. 만약에 스택에 있는 탑이 더 높다면 그 탑이 신호를 수신할 테니 출력을 해주고 이후에 나올 탑들에도 영향을 줄 수 있기 때문에 스택에 push 해주기

이런 식으로 풀면 된다.

이 문제에서는 높이와 인덱스 둘 다 신경써야 하기 때문에 Tower 라는 구조체를 선언했다.

그리고 이제 입력을 받음과 동시에 스택에 있는 값들과 비교를 해주어야 한다.

위의 1번 조건을 생각해보면 스택은 비지 않아야하고, stack.peek() 을 한 값이 현재의 높이 이하라면 전부 pop 해주어야 한다.

int curHeight = Integer.parseInt(st.nextToken());

while (!stack.isEmpty() && stack.peek().height <= curHeight) {
	stack.pop();
}

이렇게 하고 만약 스택이 비었다면 0을, 그렇지 않다면 스택에서 뽑은 값의 인덱스를 출력하고 다시 스택에 넣어주면 된다.

---

코드

import java.io.*;
import java.util.*;
public class Main_2493 {
	static class Tower {
    	int height;
    	int index;

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

  	static int n;
  	static Stack<Tower> stack;
  	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringBuilder sb = new StringBuilder();

    	n = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	stack = new Stack<>();

    	for (int i = 0; i < n; i++) {
      		int curHeight = Integer.parseInt(st.nextToken());

      		while (!stack.isEmpty() && stack.peek().height <= curHeight) {
        		stack.pop();
      		}

      		if (stack.isEmpty()) {
        		sb.append("0 ");
      		} else {
        		sb.append(stack.peek().index).append(" ");
      		}
      		stack.push(new Tower(curHeight, i + 1));
    	}
	 	System.out.println(sb);
    }
}