백준 2493 탑 - Java 자바 문제 풀이

문제 해설

 n개의 탑이 일직선으로 세워져 있습니다. 이 탑들의 꼭대기에서는 무조건 왼쪽 방향으로 레이저 빔이 나가는데, 그 신호를 수신하는 건 가장 먼저 레이저를 맞는 단 하나의 탑입니다. 각 탑에서 쏘는 레이저를 몇 번째 탑이 맞는지 구하는 문제입니다.

 

문제 풀이 계획

필요 변수

변수명	타입	초기값	설명
N	int		탑의 개수
stack	Stack<Tower>		Tower 객체를 저장하는 스택
X	Tower {     int height;     int index; }		Tower 클래스, 각 탑의 높이와 인덱스(순서)를 갖는다.

 

해결 로직

 주어진 탑의 개수 N의 범위가 1 이상 500000 이하인데 1.5초 시간제한을 가지므로, O(n) 시간 안으로 해결해야 합니다. (1억 번 연산 ≒ 1초) 따라서 각 탑의 높이를 배열에 저장하고, 뒤에서 부터 앞으로 2중 for문으로 값을 비교하는 풀이(먼저 나왔던 나보다 큰 탑들 중에서 가장 가까운 탑을 찾는 풀이)는 O(n^2)으로 시간초과가 납니다.

1. 탑의 개수 N을 입력 받는다.
2. 현재 탑의 height와 index(몇 번째 탑인지)를 Tower 객체에 저장한다.
3. 현재 탑 보다 작은 탑들은 모두 pop하고, 큰 탑을 만나면 해당 탑의 index를 출력한 후 현재 탑을 stack에 push 한다.

 스택을 활용하면 더 빠르게 해결할 수 있습니다.각 탑의 높이를 입력 받을 때 마다 앞서 나왔던 탑들 중 나보다 높이가 작은 탑들은 pop합니다. 왜냐하면 어차피 지금 이 탑 보다 높이가 작을 경우, 지금의 탑에 가려져 레이저 빔을 수신하지 못하기 때문입니다. 스택을 pop 하다가 지금의 탑 보다 큰 탑(먼저 입력 받았던)을 만나면 해당 탑의 index를 출력(지금 탑의 레이저 빔을 받아주는 탑)하고, 스택에 지금의 탑을 push합니다.

 

풀이 코드

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;

public class Main {
	
	public static int N;
	public static Stack<Tower> stack = new Stack<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		// 1. N을 입력 받는다.
		N = Integer.parseInt(st.nextToken());
		stack.push(new Tower(100000001,0)); // 인덱스가 0인 높이가 가장 큰 탑
		st = new StringTokenizer(br.readLine());
		
		for(int i=1; i<=N; i++) {
			int curHeight = Integer.parseInt(st.nextToken()); 
			
			Tower tower = new Tower(curHeight,i); // 지금 탑 객체(높이, 현재 인덱스) 생성
			
			// 2. 지금 탑 보다 작은 탑들은 모두 pop 한다.
			while(stack.peek().height < curHeight) {
				stack.pop();
			}
			
			// 3. 지금 탑 보다 최초로 큰 탑의 인덱스를 출력한다.
			sb.append(stack.peek().index).append(' ');
			stack.push(tower);
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}	
}

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

 

2493번: 탑