[백준 2493번][Java] 탑 - Stack

www.acmicpc.net/problem/2493

2493번: 탑

 

왜 스택구조인가?

 

먼저 아래의 상황을 관찰해보자.

 

 

먼저 i번째 건물에서 신호 보내는 상황을 살펴보면, i 건물에서 보낸 신호가 i-2에 닿고 있다.

다음 i+1에서 신호를 보낼 때는 i 건물에 신호가 닿는다. 여기서 i-1 건물에 살짝 주목해보자.

이 건물의 정보는 저장할 필요가 없다.  i+1 위치에서 보면 i 건물에 가려 보이지 않기 때문이다. 그렇기 때문에 i번째 단계에서 i 건물보다 낮은 건물의 정보는 모두 제거할 수 있다. 

 

로직이 탄생했다!

i 건물이 신호를 보낼 때, 왼쪽 방향으로 순회하면서 i 건물보다 낮은 건물의 정보는 삭제한다. 그리고 i 건물의 높이보다 크거나 같은 건물이 존재한다면 그 건물이 신호를 받는 건물이다.

 

이제 슬슬 스택 구조의 그림자가 드리워지기 시작한다. 우리가 신경쓸 부분은 이전 데이터의 끝부분만 순회하면서 처리하면 되기 때문.

 

저장된 데이터 중 i 건물보다 낮을 경우 pop 한다. 그리고 i 건물보다 높은 건물의 경우 신호를 받은 건물이므로 데이터를 기록하고 i건물을 스택에 저장한다. 그리고 가장 큰 건물이 나타나 스택을 비울 경우, 신호를 받을 건물이 없다는 처리를 한다.

 

import java.io.*;
import java.util.ArrayDeque;
import java.util.Stack;
import java.util.StringTokenizer;

/*
탑
https://www.acmicpc.net/problem/2493
 */
public class Main {
	static int n;
	static int[] receivers;
	static Building[] buildings;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		n = reader.readInt();
		buildings = new Building[n+1];
		receivers = new int[n+1];
		StringTokenizer st = new StringTokenizer(reader.readLine());
		for (int i = 1; i <= n; i++) {
			buildings[i] = new Building(i,Integer.parseInt(st.nextToken()));
		}

		solve();
		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			sb.append(receivers[i]+" ");
		}
		sb.deleteCharAt(sb.length()-1);
		System.out.println(sb.toString());
	}

	private static void solve() {
		Stack<Building> stack = new Stack<>();
		stack.add(buildings[1]);
		receivers[1] = 0;

		int index = 2;
		while(index <= n) {
			if(stack.isEmpty()) {
				stack.add(buildings[index]);
				receivers[index] = 0; index++;
				continue;
			}

			//top의 높이가 더 작으면 스택에 빼낸다.
			Building top = stack.peek();
			if(top.height < buildings[index].height) {
				stack.pop(); continue;
			}

			//top의 높이가 더 큰거나 같은 경우
			stack.add(buildings[index]);
			receivers[index] = top.id;
			index++;
		}

	}
}
class Building {
	int id, height;

	public Building(int id, int height) {
		this.id = id;
		this.height = height;
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}
	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}