탑

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

풀이

스택을 이용해서 풀면된다.

하지만 만약 스택에 미리 인풋값을 다 집어넣고 하나씩 빼면서 검사를 하게 되면 시간복잡도가 n^2이기 때문에 시간초과가 된다.

그래서 시간복잡도가 n으로 해결할 방법을 찾아야 한다.

방법은

입력으로 들어온 값에 대해 하나씩 스택에 넣으면서 판정하는 것이다.

만약 스택이 비어있는 상태면 지금 들어오는 탑이 제일 앞에 있는 것이고 탑이 레이저를 발사해도 아무곳에도 도달하지 않는다. 따라서 0이 된다.

만약 스택이 비어있지 않고 현재 스택의 탑보다 작은 값이 들어오면 스택의 탑의 번호가 된다.

이런 방법으로 풀면 시간복잡도가 n으로 풀이가 된다.

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		Stack<Pair> tower = new Stack<>();
		
		String[] line = br.readLine().split(" ");
		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(line[i]);
			while(!tower.isEmpty() && tower.peek().height < num) {
				tower.pop();
			}
			if(tower.isEmpty()) {
				sb.append(0).append(" ");
			}
			else
				sb.append(tower.peek().idx + 1).append(" ");
			tower.push(new Pair(i, num));
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}

class Pair {
	public int idx;
	public int height;

	public Pair(int idx, int height) {
		super();
		this.idx = idx;
		this.height = height;
	}

}