[Programmers] 고득점 Kit - Stack/Queue : 탑 #42588

문제 링크

탑

문제 조건

• heights는 길이 2 이상 100 이하인 정수 배열이다.
• 모든 탑의 높이는 1 이상 100 이하이다.
• 신호를 수신하는 탑이 없으면 0으로 표시한다.

변수 설명

• Top : 매개변수 heights의 idx(Index), height(높이)를 멤버 변수로 갖는다.
• ln : 매개변수 heights의 길이
• st : class Top을 타입으로 하는 스택

코드 설명

• 맨 오른쪽 index 탑을 기준으로 잡는다.
• 스택이 비어있으면 기준 index를 push해준다.
• 스택이 비어있지않으면 스택에 있는 탑과 비교해준다.
• 스택에 있는 탑보다 기준 탑이 더 크다면 pop해준 뒤 answer에 탑의 위치를 넣어준다.

배운 점

• java.lang.ArrayIndexOutOfBoundsException
  • (+) answer 배열의 크기를 명시해주지 않으면 발생하는 오류!
  • (+) answer 배열의 크기를 명시해줘야 한다는 점을 배웠다.

문제 해답

import java.util.Stack;

class Top {
    int idx;
    int height;
    Top(int idx, int height){
        this.idx = idx;
        this.height = height;
    }
}
class Solution {
    public int[] solution(int[] heights) {
        Stack <Top> st = new Stack();
        int ln = heights.length;
        int[] answer = new int[ln];
        for(int i=0; i < ln - 1; i++) // 일단 0으로 초기화
            answer[i] = 0;

        for(int i=ln-1; i>=0; i--){
            while(!st.empty() && st.peek().height < heights[i]) { // stack에 data가 있다면
                answer[st.pop().idx] = i + 1;
            }
            st.push(new Top(i,heights[i])); // i에 해당하는 데이터 push
        }
        return answer;
    }
}