BOJ 2493 탑 G5 Java

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

2493번: 탑

 

 

처음꺼보다 큰지 작은지를 비교해야함.

전형적인 stack 자료구조

1.5초 가 마음에 조금 걸리긴한다.

스택을 생각못했다면 배열로 해야하는데 50만번 x 50만번 연산을 진행해야하므로 불가.

입력받으면서 처리해볼 수도 있지 않을까? => 왼쪽으로 쏘는 것이기 때문에 받는것의 다음것을 알아야풀 수 있다. 

다 받아놓고 처리해야한다.

배열은 결국 이미 정렬된 것 중에 마지막에 들어간 것이 처음 나오는 것이 스택이므로 스택을 사용해야한다.

 

스택에는 높이와 인덱스를 담아야한다. 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class 탑 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in ));
		int N= Integer.parseInt(br.readLine());
		StringBuilder sb =new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int height = 0;
		Stack<int[]> s = new Stack<>();
		
		for(int i=1; i<=N; i++) {
			height = Integer.parseInt(st.nextToken());
			while(!s.isEmpty()) {
				if(s.peek()[1] > height) {
					System.out.print(s.peek()[0]+" ");
					break;
				}
				s.pop();
			}
			if(s.isEmpty()) {
				System.out.print(0+" ");
			}
			s.add(new int[] {i, height});
		}
		
	}
	
}

5
6 9 5 7 4

//예제입력

1. 초기 상태:
   • 스택은 비어있습니다.
2. 첫 번째 높이(6):
   • 6이라는 높이를 스택에 추가합니다. (인덱스 1)
   • 현재 스택: [ (1, 6) ]
3. 두 번째 높이(9):
   • 스택의 맨 위 탑의 높이(6)보다 현재 높이(9)가 높으므로, 6번 탑이 9번 탑에게 신호를 보냅니다.
   • 9를 스택에 추가합니다. (인덱스 2)
   • 현재 스택: [ (2, 9) ]
4. 세 번째 높이(5):
   • 스택의 맨 위 탑의 높이(9)가 현재 높이(5)보다 높으므로, 9번 탑이 5번 탑에게 신호를 보냅니다.
   • 5를 스택에 추가합니다. (인덱스 3)
   • 현재 스택: [ (2, 9), (3, 5) ]
5. 네 번째 높이(7):
   • 스택의 맨 위 탑의 높이(5)보다 현재 높이(7)가 높으므로, 5번 탑이 7번 탑에게 신호를 보냅니다.
   • 7을 스택에 추가합니다. (인덱스 4)
   • 현재 스택: [ (2, 9), (4, 7) ]
6. 다섯 번째 높이(4):
   • 스택의 맨 위 탑의 높이(7)보다 현재 높이(4)가 낮으므로, 7번 탑이 4번 탑에게 신호를 보냅니다.
   • 4를 스택에 추가합니다. (인덱스 5)
   • 현재 스택: [ (2, 9), (4, 7), (5, 4) ]
7. 결과 출력:
   • 스택에 남아 있는 정보를 기반으로 결과를 출력합니다.
   • 출력: 0 0 2 2 4 (각 탑이 받은 신호를 보낸 탑의 인덱스)