[Programmers] 고득점 Kit - Stack/Queue : 기능개발 #42586

문제 링크

기능 개발

문제 조건

• 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있다.
• 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다.
• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하이다.
• 작업 진도는 100 미만의 자연수이다.
• 작업 속도는 100 이하의 자연수이다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정한다.
• 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어진다.

변수 설명

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

코드 설명

• progresses와 speeds의 원소를 각각 큐에 넣는다.(proQ, speedQ)
• 첫 번째 원소부터 기능 개발이 완료되는데 걸리는 days를 구한다.
• 다음 원소부터 기능 개발이 완료된 개수를 complete에 더해준다.
• 기능 개발이 미완료될 때까지 complete를 더해준 뒤, complete 값을 vector 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;
    }
}