2493 - 탑 (Java)

 

---

 

문제

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

 

풀이

스택을 활용한 문제이다.

 

스택을 활용해서 내 기준 왼쪽편에 나보다 큰 건물을 빠르게 찾을 수 있다.

 

스택에는 [건물번호, 건물높이] 형태로 저장하며,

 

case 1. 스택이 빈 경우에는 -> 앞에 나보다 큰 건물이 없다는 뜻, 0번으로 세팅하고 스택에 현재 건물을 넣어준다.

 

case 2. 스택 값이 건물높이가 나보다 작다면

           -> 스택 값이 나보다 클 때까지 빼준다. (스택에 있는 높이가 크다면 내가 찾던 가장 가까운 건물을 의미한다.)

           -> 큰 값이 나오면 해당 건물 번호로 세팅해주고, 스택에 현재 건물을 넣어준다.

 

정리하면 스택에서 현재 건물보다 큰 값이 나올때까지 빼주다가, 큰 값이 나오면 해당 건물번호로 세팅해주고, 지금 건물을 넣어주고를 반복하면 된다.

 

코드

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;

public class Main {

    public class TOP{
        public int number;
        public int height;

        public TOP(int number, int height) {
            this.number = number;
            this.height = height;
        }
    }


    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        List<Integer> numbers = new ArrayList<>(Arrays.asList(br.readLine().split(" ")))
                .stream()
                .map(Integer::parseInt)
                .collect(Collectors.toList());

        int[] answer = new int[n];

        Stack<TOP> st = new Stack<>();

        for (int i = 0; i < n; i++) {

            TOP currentTOP = new TOP(i+1, numbers.get(i));

            while(!st.isEmpty()){
                // 스택 상위 값이 나보다 크거나 같은 경우
                if(st.peek().height >= currentTOP.height) break;

                // 작은 경우는 빼준다.
                st.pop();
            }

            // 만약 비어있다면 더 큰 건물이 없다는 뜻.
            if(st.isEmpty()){
                answer[i] = 0;
                st.push(currentTOP);
                continue;
            }
            answer[i] = st.peek().number;
            st.push(currentTOP);

        }

        for(int i=0; i<n; i++){
            System.out.print(answer[i]+ " ");
        }

    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기

 

뭔가 스택 느낌이 빡 왔는데 맞았다