프로그래머스 코딩테스트 연습_스택/큐_탑

모든 신호는 왼쪽으로만 쏘기 때문에 가장 오른쪽에 있는 탑부터 수신 탑을 찾는게 편하다고 생각했다.

가장 마지막 탑의 답을 가장 먼저 찾는 것은 후입 선출과 비슷하다고 생각해서 Stack으로 구현했다.

변수 선언

int rear //현재 비교하는 Stack.pop 값의 앞 인덱스를 저장할 변수
int pop //Stack.pop의 값을 저장할 변수

반복문

먼저 Stack에 탑의 높이 값들을 push했다.

Stack에서 pop을 통해 현재 탑의 높이를 저장한다.

현재 탑 높이의 이전 인덱스를 rear에 저장했으므로 rear를 통해 앞선 탑들 중 현재 탑보다 높은 탑을 찾는다.
만약 높은 탑이 있다면 그 탑의 순서를 저장하고, break 후 다음 탑의 수신탑을 찾는다.

탑이 없는 경우는 int형 배열은 기본 선언 초기값이 0이기 때문에 따로 저장하지 않았다.

import java.util.Stack;

class Solution {
    public int[] solution(int[] heights) {
        int[] answer = new int[heights.length];
        int rear = heights.length - 2;
        int pop = 0;
        
        Stack<Integer> stack = new Stack<>();
        
        for(int i = 0; i < heights.length; i++){
            stack.push(heights[i]);
        }
        
        while(!(stack.isEmpty())){
            pop = stack.pop();
            for(int i = rear; i >= 0; i--){
                if(heights[i] > pop){
                    answer[rear + 1] = i + 1;
                    break;
                }
            }
            rear--;
        }
        return answer;
    }
}