<Algorithm> 203. 탑(BJO)

1. 2493번 탑

   사용 알고리즘 : 스택

• 처음에 배열로 풀어보고 이후에 스택문제라 스택으로도 풀어보았다. 똑같은 로직으로 해서 속도차이는 크게 없었다.

• 주의 할점은 5 1 1 3 1 2 형태나 3 3 1 3 형태에서 크기가 같은 빌딩에 대한 예외처리가 필요했다. 이 부분때문에 조금 오래 걸렸다. 

문제에 대한 접근&생각

1. 탑은 각각 크기를 가지고 있음-> 오른쪽에서 왼쪽으로 레이저를 발사함 -> 레이저는 하나의 빌딩에만 수신-> 일직선(작으면 통과) 
2. 왼쪽부터 탐색 -> 빌딩 크기 비교(왼쪽이 크거나 같을경우 바로 왼쪽에 도달) -> 작을경우 클때까지 탐색  -> 스택!

코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        /******************************
         * 스택을 이용하여 이전 빌딩이 더 클 경우
         * 같을 경우 인덱스를 저장한다. 작을 경우는
         * 스택안의 빌딩들을 차례로 비교하면서
         * 수신되는 빌딩의 인덱스를 찾는다. 
         *******************************/
        int[] bu = new int[n]; 
        int[] rcv = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            bu[i] = Integer.parseInt(st.nextToken());
        }
        Stack<Integer> stack = new Stack<>();
        rcv[0] = -1;
        for(int i = 1; i < n; i++) {
            if(bu[i-1]>=bu[i]) {
                rcv[i] = i-1;
                stack.push(i-1);
            }else {
                    while(!stack.isEmpty()&&(bu[stack.peek()] <= bu[i])) {
                        stack.pop();
                    }
                    if(stack.empty()) {
                        rcv[i] = -1;
                    }else {
                        rcv[i] = stack.peek();
                    }
                    stack.add(i);
                }
            }
        
        Arrays.stream(rcv).forEach(ele->{
            System.out.print((ele<0?0:ele+1)+" ");
        });
    }
}
 
public class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] bu = new int[n]; 
        int[] rcv = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            bu[i] = Integer.parseInt(st.nextToken());
        }
        int high = 0;
        rcv[0] = -1;
        for(int i = 1; i < n; i ++) {
            if(bu[i-1] >= bu[i]) {
                rcv[i] = i-1;
                high = i-1;
            }else {
                rcv[i] = high;
                if(bu[high] < bu[i]) {
                    while(true) {
                        high = rcv[high];
                        if(high == -1||bu[high]>=bu[i]) break;
                    }
                    rcv[i] = high;
                    high = i;
                }
            }
            
        }
        Arrays.stream(rcv).forEach(ele->{
            System.out.print((ele<0?0:ele+1)+" ");
        });
    }
}