알고리즘 공부

백준 -탑

컴퓨터과학 2024. 3. 30. 21:00

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

 

2493번: 탑

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

www.acmicpc.net

흠 아무리 봐도 스택 문제보단 그리드 문제같은 문제 ... ㅎㅎ ;; 

시간 복잡도랑 메모리 초과 문제가 발생할수 있습니다.

시간 복잡도는 O(N^2)를 회피해야합니다.

최대한 O(N) 가깝게 for  문을 돌려야 하네요. ㅎㅎ 

import java.util.*;
import java.io.*;

public class Main {
	public static class Tower{
		public long tower;
		public long index;
		public Tower(long tower,long index) {
			this.tower=tower;
			this.index=index;
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(bf.readLine());
		
		long tower[]=new long[n];
		long send[]=new long[n];
		
		StringTokenizer stmp=new StringTokenizer(bf.readLine()," ");
		Stack<Tower> stacks=new Stack<>();
		for(int i=0 ;i<n;i++) {
			tower[i] = Long.parseLong(stmp.nextToken());
			while(!stacks.isEmpty()) {
				if(tower[i]>stacks.peek().tower) {
					stacks.pop();
				}else {
					System.out.print(stacks.peek().index+" ");
					break;
				}
			}
			//9 5 7
			if(stacks.empty()){
	            System.out.print(0 + " ");
	        }
			stacks.push( new Tower (tower[i], i+1 ));
		}
		
		
	}
}