[프로그래머스] 기능개발 (Java)

문제 정보

 

프로그래머스

 

교훈점

1. [5, 10, 1, 1, 20, 1] 에서 모든 배열의 원소값을 [0] 인덱스의 값 만큼 빼서 [0, 5, -4, -4, 15, -4] 로 만들고 싶을 때 아래와 같이 코드를 작성하면 안된다.

for(int i=0; i<speeds.length; i++) {
    deploy[i] -= deploy[0];
}

왜냐하면 deploy[0]의 값이 0으로 바뀌어서 i가 1부터는 deploy[1] -= 0; 의 꼴이 되어버린다.

 

이런 경우 아래 코드와 같이 deploy[0] 을 다른 변수에 저장해두고 사용해야 한다.

int minus = deploy[0];

for(int i=0; i<speeds.length; i++) {
    deploy[i] -= minus;
}

 

 

1. 배열로 풀이 O(n^2)

1. 배포까지의 걸리는 일 수를 구한다.

2-1. 순회하면서 남은 기간이 있는 경우 그 남은 기간을 빼준다. + 정답 배열에 combo 횟수만큼 넣는다.

2-2. 순회하면서 남은 기간이 0 이하인 경우 combo 횟수를 늘려준다.

import java.util.*;

class Solution {
    static int[] deploy;
    public ArrayList<Integer> solution(int[] progresses, int[] speeds) {
        deploy = new int[speeds.length]; // 배포까지 걸리는 일 수
        ArrayList<Integer> answer = new ArrayList<>();
        
        // 1. 배포까지의 일수 구하기
        getDeployDays(speeds.length, progresses, speeds);
        
        // 2. 배열을 활용하여 정답 구하기
        int combo = 0;
        
        // 처음 - 남은 기간이 있는 경우 전체 일수를 빼준다.
        // [5 10 10 1 20 1] -> [0 5 5 -4 15 -4]
        deployArrMinus(deploy[0], 0, speeds.length);
        
        for(int i=0; i<speeds.length; i++) {
            // 남은 기간이 있는 경우 전체 일수를 빼준다.
            // [5 10 10 1 20 1] -> [0 5 5 -4 15 -4]
            if(deploy[i] > 0) { 
                deployArrMinus(deploy[i],i,speeds.length);
                answer.add(combo);
                combo = 0;
            }
            
            if(deploy[i] <= 0) { // 남은 기간이 없는 경우
                combo++;
            }
        }
        // 마지막 처리
        answer.add(combo);
        
        return answer;
    }
    
    // 1. 배포까지의 일수 구하기 logic
    public static void getDeployDays(int taskCnt, int[] progresses, int[] speeds) {
        for(int i=0; i<taskCnt; i++) {
            if((100-progresses[i]) % speeds[i] == 0) {
                deploy[i] = (100-progresses[i]) / speeds[i];
            }
            else {
                deploy[i] = ((100-progresses[i]) / speeds[i])+1;
            }
        }
    }
    
    // 2. 해당 일수를 전체 순회하면서 해당 일수(minus)만큼 빼주기 logic
    // Ex. [5 10 10 1 20 1] -> [0 5 5 -4 15 -4]
    public static void deployArrMinus(int minus, int startIdx, int taskCnt) {
        for(int i=startIdx; i<taskCnt; i++) {
            deploy[i] -= minus;
        }
    }
}

 

2. Monotonic Stack으로 풀이 O(n)

배열의 순서를 바꾸면 안되고 (순서가 고정된 상태에서) 각 element를 비교하면서 처리해야 하는 유형인 경우 Monotonic Stack으로 해결할 수 있다.

 

1. 배포까지의 걸리는 일 수를 구한다.

2. Monotonic Stack을 통해 스택을 내림차순으로 두도록 하고, O(n)으로 해결

 

Monotonic Stack 개념 확인하기

[Stack 응용] Monotonic Stack

 

import java.util.*;

class Solution {
    static int[] deploy;
    public ArrayList<Integer> solution(int[] progresses, int[] speeds) {
        deploy = new int[speeds.length]; // 배포까지 걸리는 일 수
        
        // 1. 배포까지의 일수 구하기
        getDeployDays(speeds.length, progresses, speeds);
        
        // 2. Monotonic Stack을 활용하여 각 지점에서 시작해서 최초로 커지는 지점을 계산
        Deque<Integer> s = new ArrayDeque<>();
        ArrayList<Integer> answer = new ArrayList<>();
        int comboDeployCnt = 0; // 연속해서 배포되는 갯수
        for(int i=0; i<speeds.length; i++) {
        	// 만약 일정이 더 긴 것이 들어오면 연속해서 할 수 없다.
            // 스택에서 일정이 더 긴 것을 발견할 때까지 pop을 하고 연속으로 완료된 배포 수를 추가해준다.
            while(!s.isEmpty() && deploy[s.peek()] < deploy[i]) { 
                comboDeployCnt++;
                s.pop();
            }
            
            if(s.isEmpty() && i != 0) {
                answer.add(comboDeployCnt);
                comboDeployCnt = 0;
            }
            
            s.push(i);
        }
        
        // 스택에 남은 값 처리
        while(!s.isEmpty()) {
            comboDeployCnt++;
            s.pop();
        }
        answer.add(comboDeployCnt);
        
        return answer;
    }
    
    // 1. 배포까지의 일수 구하기 logic
    public static void getDeployDays(int taskCnt, int[] progresses, int[] speeds) {
        for(int i=0; i<taskCnt; i++) {
            if((100-progresses[i]) % speeds[i] == 0) {
                deploy[i] = (100-progresses[i]) / speeds[i];
            }
            else {
                deploy[i] = ((100-progresses[i]) / speeds[i])+1;
            }
        }
    }
}