[JAVA] 백준 2493 - 탑

문제 링크

문제 이해

탑이 N개 있음. 각각의 탑들은 왼쪽으로 레이저 신호를 발사함. 각각의 탑들이 레이저 신호를 발사했을 때, 그 레이저 신호를 수신하는 탑들의 인덱스 번호를 출력하는 것임.

예제 입력으로 6 9 5 7 4 가 있음.

6은 왼쪽으로 레이저 쏴도 수신하는 탑이 없으니까 0
9는 왼쪽으로 레이저 쏴도 9보다 높은 탑이 없으니까 0
5는 왼쪽으로 레이저 쏘면 높이가 9인 탑이 수신하므로 2
7은 왼쪽으로 레이저 쏘면 높이가 9인 탑이 수신하므로 2
4는 왼쪽으로 레이저 쏘면 높이가 7인 탑이 수신하므로 4

문제 풀이

스택으로 풀면 된다는 힌트를 받고 문제를 보기 시작했다.

처음엔 스택으로 어떻게 푸는지 오히려 난감했었는데 하나하나 따지고 보니 스택이 맞았다.


제일 처음에는 탑들이 들어올 때 제일 가까이 있는 탑부터 for문으로 순회해서 따져볼까 했지만 N이 500,000 이하라서 시간초과 뜰 수도 있을 것 같아서 포기했다.

스택으로 어떻게 풀지 고민하다가 떠오른 실마리가 있었다.

예제 입력처럼 스택에 6이 있고 9가 들어오게 되면 6은 필요가 없어진다는 것이다.

레이저는 왼쪽으로만 쏘기 때문이다.

예제 입력인 6 9 5 7 이 순서대로 들어온다고 하면 9 7 만 남게 된다.

이후에 4가 들어오면 9 7 4만 스택에 남게 된다.

내림차순으로만 남기는 것이다.


이 실마리를 구체화시켜서 코드를 짰다.

전체적으로 3개의 경우로 나누어서 구현했다.

스택이 비어있을 때 / 스택 peek의 높이가 새로 들어올 높이보다 클 때 / 작을 때

새로 들어온 Top 객체 t 생성
if (스택이 비어있음) stack.push(t); 0 출력;
else if (스택peek의 높이 > t의 높이) 스택peek의 idx 출력; stack.push(t);
else {
	for(스택 크기만큼):
		if(스택peek의 높이 < t의 높이) stack.pop();
		else 스택peek의 idx 출력; stack.push(t);

코드

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());

		Stack<Top> top = new Stack<Top>();
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=N; i++) {
			int h = Integer.parseInt(st.nextToken()); //새로운 탑의 높이
			Top t = new Top(i, h); 
			
			int sendIdx = 0; //새로운 탑에게 레이저신호 받는 탑의 idx
			
			if(top.empty()) { //스택에 아무것도 없을 때
				top.push(t);
				sb.append(sendIdx + " ");
				continue;
			}else if(top.peek().num > h) { //스택 젤 위의 탑이 바로 레이저 신호 받을 때
				sb.append(top.peek().idx+" ");
				top.push(t);
				continue;
			}
			
			//바로 레이저 신호를 받지 못해서 스택을 순회해야할 때
			for(int j=top.size()-1; j>=0; j--) {
				if(top.peek().num < h) { //새로 들어올 탑보다 높이 낮으면 이후에 레이저 신호 받을일 없으니까 pop
					top.pop();
				}else { //새로 들어올 탑보다 높으면 레이저 신호 받음
					sendIdx = top.peek().idx;
					break;
				}
			}
			sb.append(sendIdx+" ");		
			top.push(t);
			
		}

		System.out.println(sb);
	}
}
class Top{
	int idx; 
	int num;
	public Top() {}
	public Top(int idx, int num) {
		super();
		this.idx = idx;
		this.num = num;
	}
	
}