알고리즘 공부
백준 -탑
컴퓨터과학
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 ));
}
}
}