[백준] 2493 탑 - 자료구조 Stack(스택) JAVA

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

2493번: 탑

코드설명

자료구조인 Stack 을 활용하는 문제입니다.

 

문제접근과정을 정리해보면, 

 1 <= N <= 500,000 일경우, 모든 과정을 for문으로 찾을경우 O(N^2)로 시간복잡도를 초과합니다.
- 처음에  이분탐색의 시간복잡도 O(log N) 으로 해결해보려고했지만, 탑의 마지막 크기인 4보다 크면서, 가장 4와 가까운 위치의 탑을 구하는 것을 이분탐색으로 구하기에 명확하게 아이디어가 떠오르지 않았습니다. + 이분탐색의 경우 정렬이 되어있어야하지만, 정렬이 되어서 해결하는 아이디어가 떠오르지 않았습니다.

- 혹은 파라매트릭 서치를 이용해서 풀어보려했지만, 해당 알고리즘들을 활용하여 해결하는것에 대한 아이디어가 떠오르지 않았습니다.  일반적으로 파라매트릭 서치를 활용하여 풀어본다면, 탑의 최소값과 최대값을 찾은뒤 각 탑의 값들을 만족하는 숫자를 찾는다면 사용할 수 있겠지만, 이 문제의 경우 5개의 각 탑에 대한 것을 진행하기에 어떻게 활용해야할지 감이 오지 않았습니다.

 

Stack을 활용하는 경우의 시간복잡도는 O(N)입니다. Stack 자료구조의 시간복잡도는

• Insertion O(1)
• Deletion O(1)
• Search O(n) 

 

문제예시를 통해 Stack을 활용하는경우의 로직입니다. 

5
6 9 5 7 4

 

1. 첫 인덱스부터 Stack이 비어있다면 "0"을 출력합니다.  ( 첫번째에는 송신할 레이더가 없으므로 무조건 0 입니다.  )
   1. 첫 인덱스의 값 6 을 Stack에 push 합니다.
2. 두번쨰 인덱스인 9인 경우에, 먼저 Stack이 빌때까지 테스트를 진행합니다. Stack 값 ( "6" ) 의 Peek을 통하여 9보다 작은 경우 9의 레이저를 수신할 수 없으므로 stack을 pop 시킵니다. 이제 Stack 값은 Empty인 상태입니다.
   1. Stack이 비어있으므로 "0"을 출력합니다.
   2. Stack에 "9"를 넣습니다.
3. 세번째 인덱스인 5인 경우에, 먼저 Stack이 빌때까지 테스트를 진행합니다. Stack 값("9")를 Stack Peek을 통하여 5보다 큰경우를 찾았기에 해당 값의 Index를 출력하고, 반복문을 중단시킵니다. 해당 탑의 높이가 레이더를 수신하였기에  Stack에서 제거하지도 않습니다. 현재까지 해당 탑의 위치가 가장 큰 탑입니다.
   1. Stack에 "5"를 넣습니다.
4. 네번째 인덱스인 7인 경우에, 먼저 Stack이 빌때까지 테스트를 진행합니다. Stack 값("9", "5")를 Stack Peek을 통하여 "5"를 가져오게되고, 7보다 작으므로 "5"는 레이더를 수신하지 못합니다. 그러므로 Stack.pop을 통해 Stack값을 ("9")로 변환시킵니다. 다시 Stack Peek을 통하여 "9"를 가져오게 되고, 7보다 크므로 "9"는 레이더를 수신합니다. 해당 값의 인덱스를 출력합니다.
   1. Stack에 "7"을 넣습니다.
5.  다섯번쨰 인덱스 같은경우도 위와 똑같이 진행하면됩니다.

 

문제의 아이디어를 Stack과 함께 떠올려야하는 문제입니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, K;
	public static int[] arr;
	public static int answer = 0;
	public static Stack<Node> stack = new Stack<Node>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	for(int i=0;i<N;i++) {
    		while(!stack.isEmpty()) {
    			if(stack.peek().height >= arr[i]) {
    				System.out.print( (stack.peek().idx + 1 )+" ");
    				break;
    			}
				stack.pop();
    		}
    		
    		if(stack.isEmpty()) {
    			System.out.print("0 ");
    		}
    		
    		stack.push(new Node(i, arr[i]));
    		
    	}
    }
       
}
  

class Node{
	int idx;
	int height;
	public Node(int idx, int height) {
		this.idx = idx;
		this.height = height;
	}
}