[알고리즘]백준 2493: 탑

 

스택

해당 유형의 문제는 스택 자료구조를 사용하여 O(N)으로 문제를 해결할 수 있다.

스택에는 항상 “현재 인덱스보다 높은 탑들의 인덱스들”만 들어있다. 1부터 N까지의 인덱스를 순회하면서, 현재 인덱스보다 낮은 탑들의 인덱스를 스택에서 제거한다. 스택의 최상위에는 레이저가 처음으로 도달하는 탑의 인덱스가 항상 위치하게 된다.

Stack<Integer> stack = new Stack<>();
for(int i=1; i<=N; i++){
    while(!stack.isEmpty() && (tower[stack.peek()] <= tower[i])){
        stack.pop();
    }
    if(stack.isEmpty()) sb.append(0+" ");
    else sb.append(stack.peek()+" ");
    stack.add(i);
}

 

코드

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

//716ms, O(N)
public class Main {
    static int N;
    static int[] tower;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        tower = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) tower[i] = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        for(int i=1; i<=N; i++){
            while(!stack.isEmpty() && (tower[stack.peek()] <= tower[i])){
                stack.pop();
            }
            if(stack.isEmpty()) sb.append(0+" ");
            else sb.append(stack.peek()+" ");
            stack.add(i);
        }

        System.out.println(sb);
    }
}

 

 

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