[백준] 2493 : 탑 - 자바(JAVA)

https://www.acmicpc.net/problem/2493

2493번: 탑

 

문제 해석

 

서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세운다.

 

각 탑의 꼭대기에 레이저 송신기를 설치하였다.

 

모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있습니다.

 

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 왼쪽 방향으로 레이저를 발사할 수 있습니다.

 

그림과 같이 6, 9의 탑은 왼쪽 방향으로 레이저를 발사해도 레이저를 받아줄 탑이 존재하지 않으므로 0이 출력됩니다.

 

크기 5의 탑은 왼쪽방향으로 레이저를 발사한다면 2번 탑이 레이저를 받아주기 때문에 2를 출력합니다.

 

크기 7의 탑은 왼쪽방향으로 레이저를 발사한다면 2번 탑이 레이저를 받아주기 때문에 2를 출력합니다.

 

크기 4의 탑은 왼쪽방향으로 레이저를 발사한다면 4번 탑이 레이저를 받아주기 때문에 4를 출력합니다.

 

 

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다.

둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 빈칸을 사이에 두고 주어진다.

 

제약조건

1<= N <= 500,000

 

 

 

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다.

만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

 

문제 풀이 전 설계

탑이 왼쪽 방향으로만 레이저를 발사하기 때문에 그림을 왼쪽으로 90도 돌리게 되면 이는 스택 자료구조와 동일한 구조로 보입니다.

 

만약 스택에 넣을 때 스택의 top이 현재 들어올 탑보다 작다면 이것은 어차피 레이저를 수신하지 못하기 때문에 stack을 pop한뒤 현재 들어올 탑을 push 하게 됩니다.

 

만약 스택에 넣을 때 스택의 top이 현재 들어올 탑보다 크다면 이는 레이저를 수신할 수 있기 때문에 stack에 그대로 두고 현재 들어올 탑의 push 합니다.

 

이를 반복하며 수신한 탑의 번호를 출력해야 합니다.

 

이때 우리가 관리해야 할 것은 탑의 높이와 탑의 번호이기 때문에 높이와 번호를 갖는 Tower객체를 생성하여 Stack에서 관리합니다.

 

주의할 점 

3 2 1 4 같은 타워를 조심해야 합니다.

스택의 top보다 작은 값들이 들어오다가 큰 값이 들어오는 경우에는 스택이 비어있거나 자신보다 큰 높이를 만날 때까지 pop 해야 합니다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

class Tower {
	int index;
	int height;
}

public class Main_2493_탑 {
	static Tower[] towerArray;
	static int result[];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		inputTowerInfo();
		getSendedTowerNumber();
		printResult();
	}

	private static void inputTowerInfo() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int numberOfTower = Integer.parseInt(br.readLine());
		towerArray = new Tower[numberOfTower];
		result = new int[numberOfTower];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < numberOfTower; i++) {
			towerArray[i] = new Tower();
			towerArray[i].index = i + 1;
			towerArray[i].height = Integer.parseInt(st.nextToken());
		}
	}

	private static void getSendedTowerNumber() {

		if (towerArray.length == 1) {
			System.out.println(0);
			return;
		}

		Stack<Tower> towerStack = new Stack<Tower>();
		int preSize;
		towerStack.push(towerArray[0]);

		outer: for (int i = 1; i < towerArray.length; i++) {

			while (!towerStack.isEmpty()) {
				preSize = towerStack.peek().height;

				// 현재 타워가 더 낮은 상황
				if (towerArray[i].height <= preSize) {
					result[i] = towerStack.peek().index;
					towerStack.push(towerArray[i]);
					continue outer;
				}

				// 현재 타워가 더 높은 상황
				towerStack.pop();

				// 삭제 후에 배열이 비어있으면 push하고 다음 건물검색
				// result[i]에 대한 구문이 없는 이유는 초기화할때 기본값이 0이기 때문입니다.
				if (towerStack.isEmpty()) {
					towerStack.push(towerArray[i]);
					continue outer;
				}
			}
		}
	}

	private static void printResult() throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < result.length; i++) {
			sb.append(result[i] + " ");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}