[백준] 2493번 : 탑

문제

N개의 서로 높이가 다른 탑이 같은 수평선 상에 존재할 때

각 탑에서 발사한 레이저 신호를 어떤 탑에서 받는지를 알아내라

 

접근 방식

지문이 길어서 이해가 어려울 수도 있지만

발그림으로 그려보자면 아래 그림과 같다

 

 

높이가 낮은 탑은 자신보다 높은 가장 먼저 만나는 탑에 신호를 줄 수 있고

자신보다 높은 탑이 없다면 신호를 받는 탑이 존재하지 않는다.

 

높이가 4인 5번째 탑의 신호는 높이가 7인 4번째 탑이 받을 것이고

높이가 각각 5와 7인 3, 4번째 탑은 높이가 9인 2번째 탑이 받고

나머지 1, 2번째 탑의 신호는 받을 탑이 존재하지 않는다.

 

따라서 0 0 2 2 4가 정답이 된다.

 

첫 번째 탑부터 시작하면서 이전 탑들 중에 자신보다 높은 탑이 있는지

찾고 존재한다면 그 탑의 번호를 출력하면 되는데

이전 탑들 중에서 높이가 낮은 탑들은 빼버리고 반복하면 효율적이다.

 

 

위의 사진에서 예를 들면

어차피 5는 9에서 막힐 텐데 6을 가지고 있을 필요가 없고

나중에 9보다 큰 수가 나오더라도 이전 탑들을 들릴 필요가 없어진다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());

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

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

			if (stack.isEmpty()) {
				stack.push(new Tower(i, current));
				sb.append("0 ");
			} else {
				while (true) {
					if (stack.isEmpty()) {
						stack.push(new Tower(i, current));
						sb.append("0 ");
						break;
					}

					Tower tower = stack.peek();

					if (current < tower.height) {
						stack.push(new Tower(i, current));
						sb.append(tower.number).append(" ");
						break;
					} else {
						stack.pop();
					}
				}
			}
		}

		System.out.println(sb);
	}

}

class Tower {
	int number;
	int height;

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