1809 : 탑

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1082&sca=50&sfl=wr_hit&stx=1809&sop=and

JUNGOL | 탑 > 문제은행

카테고리는 stack이라고 되어있으나 list가 훨씬 빠른 속도를 보여줌

요소들 모두를 계속 리스트에서 관리하면 거의 당연히 시간 초과가 발생한다.  새로운 타워가 들어올 때 기존 타워가 더 작다면 의미없으므로 지워버린다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_list {

	// TODO: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1082&sca=50&sfl=wr_hit&stx=1809&sop=and
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tokens;
	static int N;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(br.readLine());

		List<Tower> towers = new ArrayList<>();
		towers.add(new Tower(0, 100000000));       // 기준 타워
		tokens = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			Tower tower = new Tower(i, Integer.valueOf(tokens.nextToken()));
			for(int j=towers.size()-1; j>=0; j--) {
				Tower prevTower = towers.get(j);
				if(prevTower.height> tower.height) {
					sb.append(prevTower.idx).append(" ");
					break;
				}else {
					towers.remove(prevTower);
				}
			}
			towers.add(tower);
		}
		System.out.println(sb);

	}

	static class Tower {
		int idx;
		int height;

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

	static String src = "5\r\n" +
			"6 9 5 7 4";
}