[백준/JAVA] 2493번: 탑

📖 문제

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

 

 

💡  풀이 방식

• 스택

필요 자료구조
- (탑 번호, 높이) 값을 저장하는 int[]형 스택

 

탑의 높이를 미리 입력받지 않아도 되고,

탑의 높이를 입력 받으면서 이미 입력받은 값들과 비교하며 풀면 된다. 

 

- 입력받은 높이가 현재 높이보다 낮은 경우, 해당 탑에는 레이저가 닿을 수 없으므로 제거(pop)한다.

- 현재 스택이 비어있다면, 레이저가 닿을 수 있는 탑이 없으므로 0을 출력한다.

 

 

 

💥 유의사항

데이터 크기가 크므로, 완전탐색을 썼다가는 시간 초과가 발생한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        Stack<int[]> stack = new Stack<>(); // (탑 번호, 높이) 저장용 스택
        
        int N = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1; i <= N ; i++) {
            int top = Integer.parseInt(st.nextToken()); // 입력받은 높이
            
            while(!stack.isEmpty()) { // 본인보다 더 큰 탑이 있는지 탐색
                if(stack.peek()[1] >= top) { // 본인보다 더 큰 탑을 찾으면, 해당 탑 번호 출력
                    sb.append(stack.peek()[0] + " ");
                    break;
                }
                
                // 입력받은 높이가 현재 높이보다 낮은 경우, 레이저가 닿을 수 없음
                stack.pop();
            }
            
            // 현재 스택이 비어있다면, 레이저가 닿을 수 있는 탑 x
            if(stack.isEmpty()) {
                sb.append("0 ");
            }
            
            stack.push(new int[] {i, top}); // (탑 번호, 입력받은 높이) 저장
        }
        
        System.out.println(sb.toString());
    }
}

 

---

💦 어려웠던 점

- 데이터 크기가 커서 완탐으로 하면 분명 시간 초과가 뜰 것 같다는 생각이 들었는데, 자료구조 중 스택을 사용할 생각은 못 했당,,

 

 

🧐 새로 알게 된 내용

- 스택을 활용하는 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준]2493: 탑 - JAVA