[문제풀이] B2493 탑

탑

---

  🪅 가장 나중에 들어오는 데이터를 먼저 검사하는 흐름을 보고 스택(Stack)을 떠올릴 수 있느냐
  🪅 헷갈리기 쉬운 정보들을 class로 묶어 정리할 수 있느냐 
  🪅 두 개의 스택으로, 한 스택에서 뺀 데이터 중 조건에 맞는 데이터만, 나머지 스택에 push할 절차를 구현할 수 있느냐
  🪅 데이터에 따라 불명확한 반복횟수를 세줄 또다른 변수를 만들 생각을 할 수 있느냐
  🪅 조건을 만족했을 시, 다음 데이터에 영향을 주지 않도록 초기화했느냐 

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

/**
 * 백준 2493번 탑
 * 
 * 입력:
 * 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 
 * 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 
 * 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.
 * 
 * 출력:
 * 첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 
 * 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.
 *
 */
class TopInfo {
    int height;
    int num;
    TopInfo(int height, int num) {
        this.height = height;
        this.num = num;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Stack<TopInfo> stack = new Stack<>();

        // stack에 입력받은 height와 번호 push
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            int height = Integer.parseInt(token.nextToken());
            TopInfo top = new TopInfo(height, i+1);
            stack.push(top);
        }

        // test 출력
        // for(int i = 0; i < stack.size(); i++) {
            // TopInfo cur = stack.get(i);
            // System.out.print(cur.height + " " + cur.num);
            // System.out.println();
        // }

        Stack<Integer> result = new Stack<>();
        int popCnt = 1;
        while(!stack.isEmpty()) {
            // 현재값
            TopInfo cur = stack.pop();
            if(!stack.isEmpty() && cur.height <= stack.peek().height) {
                for(int i = 0; i < popCnt; i++) {
                    result.push(stack.peek().num);
                }
                popCnt = 1;
            } else {
                popCnt++;
            }
        }

        for(int i = 1; i < popCnt; i++) {
            result.push(0);
        }
        // System.out.println(result);

        for(int i = 0; i < N; i++) {
            System.out.print(result.pop() + " ");
        }
    }
}

💡 문제 접근 과정
탑의 높이와 번호가 인덱스랑 헷갈릴 것 같아서 TopInfo라는 클래스를 만들었다.
조건에 맞는 데이터만 처리하는 과정은 가장 마지막에 들어온 데이터부터 진행하기 때문에
LIFO(Last In First Out) 구조를 갖는 스택을 사용할 생각을 했다.
입력받은 데이터를 스택에 차곡차곡 쌓고, 하나씩 빼면서 조건에 맞는 데이터만
다른 스택에 쌓았고, 다시 이를 빼면서 출력했다.

애먹었던 부분은 자꾸 결과가 0 0 0 2 4가 나왔는데, (정답: 0 0 2 2 4)
이는 pop한 수만큼을 다른 스택에 push했어야 했는데, 이를 놓쳤기 때문이다.
pop한 수만큼을 push하기 위해 popCnt라는 변수를 만들어야 했다.