[Java] 탑

1. 문제설명

일직선 위에 n개의 서로 높이가 다른 탑이 주어진다.
오른쪽에서 왼쪽으로 탑마다 레이저를 발사하는데 왼쪽 탑이 크면 레이저를 수신한다
이 때 각 탑마다 레이저를 수신한 탑의 번호를 출력하라
ex) 6, 9, 5, 7, 4 -> 0, 0, 2, 2, 4
높이 6, 9는 레이저를 수신한 탑이 없으니 0
높이 5 탑은 2번째 높이가 9인 탑이 수신하니 2
높이 7 탑은 2번째 높이가 9인 탑이 수신하니 2
높이 4 탑은 4번째 높이가 7인 탑이 수신하니 4

입력 형식

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력 형식

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

2. 알고리즘 접근

값을 찾을 대상의 탑을 찾기 위해 이전의 탑을 계속 조회해야 한다(큰지 작은지)

스택을 사용 한다
-> 순차적으로 값을 찾아가는데 필요없을 데이터는 뒤에서부터 삭제할 때 사용

Q. 어떤 데이터가 필요 없는 데이터인가?

위 상황에서 5번 타워는 3번 타워에 레이저를 송신할 것이다.
5번 타워에서 레이저를 송신한 후
6번타워에서 2, 4, 5번 타워에 레이저를 송신할 것인가? -> 그렇지 않다
2 < 3 , 4 < 5, 5 < 6 이기 때문

불필요한 대상 정하기

순차적으로 i가 증가할 때마다 본인보다 작은 타워를 삭제하자
그러면 가장 큰 타워가 앞에 남고 점점 작아지는 타워의 모습이 될 것이다.
ex ) t = [6, 3, 4]의 경우 순서

• 스택에 6을 저장한다 > [6]
• 3은 스택 6과 비교해 작다면 6의 인덱스번호(1)를 가리킨다, 이후 스택에 자신의 값을 추가한다 [6, 3]
• 4는 스택의 가장 마지막값 3과 비교해 더 크니 기존 스택의 끝 값을 제거하고
  또 스택의 마지막값(6)을 비교한다 더 작으니 스택에 자신을 추가하고 6의 인덱스 번호를 가리킨다

3. 소스코드

public class Main {
	public static final Scanner scanner = new Scanner(System.in);
	public static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));


	/**
	 * 파라미터로 주어지는 각 타워들에 대해 타겟 타워를 계산하는 함수
	 *
	 * @param n         타워의 수
	 * @param towers    왼쪽~오른쪽 순서로 저장된 타워 배열
	 */
	public static void findTargetTowers(int n, Tower[] towers){
		// 현재 다른 타워의 신호를 수신할 가능성이 있는 타워들
		Stack<Tower> touchableTowers = new Stack<>();
		for(Tower t : towers){ // 모든 타워에 대해
			Tower target = null;
			
			// 스택에 값이 있고, 스택에 저장된 높이가 t의 높이보다 작다면
			while(touchableTowers.size() > 0 && touchableTowers.peek().height < t.height ){
				touchableTowers.pop(); // 스택의 값을 제거한다
			}
			// 스택에는 t보다 높이가 큰 타워들이 들어있다
			if(touchableTowers.size() > 0){
				target = touchableTowers.peek(); // 타겟 타워 값을 꺼내
			}
			t.setTargetTower(target); // 타겟 타워 설정
			touchableTowers.push(t);
		}

	}

	public static void main(String[] args) throws Exception {
		int n = scanner.nextInt();

		Tower[] towers = new Tower[n];
		for(int i = 0 ; i < n ; i++) {
			int hi = scanner.nextInt();
			towers[i] = new Tower(i + 1, hi );  // 인덱스 1부터 저장
		}

		// 각 타워가 송신하는 레이저에 대해 타겟을 모두 계산한다
		findTargetTowers(n, towers);

		for(int i = 0 ; i < n; i ++) {
			if(i > 0 ){
				writer.write(" ");
			}

			Tower t = towers[i];
			if(t.getTargetTower() == null){
				writer.write("0");
			}else{
				int targetIndex = t.getTargetTower().index;
				writer.write(String.valueOf(targetIndex));
			}
		}
		writer.flush();
		writer.close();
	}

}

class Tower{
	public final int index;     // 타워의 인덱스
	public final int height;    // 타워의 높이

	private Tower targetTower;  // 이 타워의 레이저를 수신하는 대상 타워

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

	public void setTargetTower(Tower targetTower) {
		this.targetTower = targetTower;
	}

	public Tower getTargetTower() {
		return targetTower;
	}
}