[백준]2493번 탑(JAVA)

0. 문제 링크

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

2493번: 탑

 

1. 문제 설명

1) 탑들의 개수 N과 탑들의 높이가 주어짐

2) 탑 순서의 반대 방향(왼쪽 방향)으로 레이저 신호를 발사할 때, 레이저 신호를 수신한 탑들의 번호 출력하기

 

2. 입출력

// input
5
6 9 5 7 4

// output
0 0 2 2 4

 

3. 코드

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

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

public class b2493 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int N = Integer.parseInt(br.readLine()); // 탑의 수
		int[] arr = new int[N]; // 탑의 높이
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int[] ans = new int[N]; // 수신한 탑의 번호
		
		Stack<Tower> s = new Stack(); // 스택 생성
		for(int i = N-1; i >= 0; i--) {
			Tower tmp = new Tower(arr[i], i+1); // 타워 신호, 인덱스 번호 저장
			
			if(s.isEmpty()) { // 비어 있으면
				s.push(tmp); // 넣기
				
			} else { // 비어 있지 않으면
				while(!s.isEmpty()) { // 비어 있지 않을 때까지 반복
					int peekIdx = s.peek().idx; // 제일 위에 있는 idx
					int peekHeight = s.peek().height; // 제일 위에 있는 height
					if(peekHeight < tmp.height) { // 넣을 거보다 작으면
						s.pop(); // 꺼내기
						ans[peekIdx-1] = i+1; // 수신한 타워 저장
					} else {
						break;
					}
				}
				s.push(tmp); // 넣기
			}
		}
		
		for(int i = 0; i < ans.length; i++) {
			System.out.print(ans[i] + " ");
		}
		
	}
}

 

실행 결과

 

4. 회고

1) 인덱스와 탑의 높이를 저장하기 위해 Tower class 생성

2) stack을 이용하여 가장 마지막에 넣은 탑이 신호를 받을 수 있는지 판별

- 가장 마지막에 넣은 탑이 현재 넣을 탑의 높이보다 작으면, 신호를 받으므로 꺼내고, 수신한 탑의 인덱스 저장

- 가장 마지막에 넣은 탑이 현재 넣을 탑의 높이보다 크면, 신호를 받을 수 없음

- 두 작업을 진행한 후에 현재 탑은 반드시 stack에 push

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b2493.java