백준 2493번: 탑

문제 설명

접근법

• 검사하는 탑과 가까운 앞에 있을수록 레이저를 받을 가능성이 큽니다. (머리있는 탑은 가려져있을 가능성이 있기 떄문에) 늦게 확인한 값을 먼저 활용하는(LIFO) 스택을 활용합니다.
• 높이와 인덱스가 함께 필요하기 때문에 객체를 사용하면 편리합니다.
• stack에 값들과 현재 검사중인 탑의 값을 비교해 레이저를 받을 수 있는지 확인합니다.
• 검사하는 탑은 무조건 stack에 넣어야 합니다. 내 뒤에 나보다 작은 친구가 나올수도 있기 때문입니다.
• 내 앞에 나보다 작은 친구들은 더이상 레이저를 받을 수 없습니다.
  • 이들을 stack에서 빼줘 stack을 검사하는 시간을 단축합니다.

정답

package day0207;

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

public class Main_2493_탑 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N];
		String temp[] = br.readLine().split(" ");
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(temp[i]);
		}
		
		
//		int N = 6;
//		int[] arr = {6,4,5,2,5,1};

		
		int[] answer = new int[N];
		Stack<tower> stack = new Stack();
		
		stack.push(new tower(arr[0],0)); //첫번째 값을 넣습니다
		for (int i = 1; i < N; i++) { //1부터 N까지 검사합니다
			if(stack.peek().height <=arr[i]) { // 검사하는 탑이 stack의 첫번째 값(top)보다 크다면
				while (stack.isEmpty() == false) { // 나보다 큰 탑을 찾기 위해 스택을 계속 검사합니다					
					if(stack.peek().height >=arr[i]) { // 나보다 큰 탑을 찾았다면
						answer[i] = stack.peek().idx+1; // 그 친구가 내 레이저를 받아줍니다.
						break; // 레이저를 받았기 때문에 스택을 그만 검사합니다
					}
					stack.pop(); // 나보다 작은 탑들은 앞으로 레이저를 맞을 일이 없기 때문에 스택에서 빼줍니다 
				}
				stack.add(new tower(arr[i],i)); // 나는 일단 무조건 스택에 한번 넣습니다
			}else {// 검사하는 탑이 stack의 첫번째 값보다 작다면
				answer[i] = stack.peek().idx+1; // 바로앞에서 내 레이저를 받아줍니다
				stack.add(new tower(arr[i],i)); // 나는 일단 무조건 스택에 한번 넣습니다
			}
		}
		for (int i = 0; i < answer.length; i++) {
			sb.append(answer[i]+" ");
		}
		System.out.println(sb.toString().substring(0,sb.length()-1));
		
	}
	
}
// 높이와 인덱스를 함께 저장하기 위해 클래스를 만듭니다.
class tower{
	int height;
	int idx;
	tower(int h,int i){
		this.height = h;
		this.idx = i;
	}
}