[programmers-lv2] 기능개발

[programmers-lv2] 기능개발

🙋‍♂️ 들어가며

이 문제를 보니 Queue의 느낌이 들었고, 병원 접수표를 뽑고 대기하는 FIFO과 같은 영역에 해당 알고리즘을 활용할 수 있겠다는 생각이 들었다.

거두절미하고 이번 문제에서는 조건을 보니 O(N^2)가 충분히 가능하고, O(N)도 가능하겠다.

그래서 총 2가지 풀이를 준비하였다

개발 완료시간을 배열로 만들어서 푸는 문제였다

testcase 1,2의 경우 각각 완료시간은 아래와 같겠다

testcase-1

int[] end_time = new int[] {7, 3, 9};

testcase-2

int[] end_time = new int[] {5, 10, 1, 1, 20, 1};

✅ 2중 반복문

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        
        // 1. 각 작업의 종료시간을 만들자
        int N = speeds.length;
        int[] answer = new int[N];
        int[] end_time = new int[N];
        for (int i = 0; i < N; i++) {
            int cur_end_time = (int) Math.ceil( (100 - progresses[i]) / (double) speeds[i] );
            end_time[i] = cur_end_time;
        }
        
        // 2. 종료시간 배열 값 추가
        int size_idx = 0;
        int start_idx = 0;
        while (start_idx < N) {
            int temp_cnt = 1;
            for (int next_idx = start_idx + 1; next_idx < N; next_idx++) {
                // 2-1. 만약 현재 숫자보다 다음 숫자가 작거나 같다면
                if (end_time[start_idx] >= end_time[next_idx]) {
                    temp_cnt++;
                }
                // 2-2. 더 크면 break
                else if (end_time[start_idx] < end_time[next_idx]) break;
            }
            
            // 2-3. 배열에 추가
            answer[size_idx] += temp_cnt;
            size_idx++;
            
            // 2-4. 다음 시작 idx 갱신
            start_idx += temp_cnt;
        }
        
        // 3. 결과 배열 반환
        int[] res = new int[size_idx];
        for (int i = 0; i < size_idx; i++) {
            res[i] = answer[i];
        }
        
        return res;
    }
}

✅ O(N)

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        
        // 1. 각 작업의 종료시간을 만들자
        int N = speeds.length;
        int[] answer = new int[N];
        int[] end_time = new int[N];
        for (int i = 0; i < N; i++) {
            int cur_end_time = (int) Math.ceil( (100 - progresses[i]) / (double) speeds[i] );
            end_time[i] = cur_end_time;
        }
        
        // 2. 종료시간 배열 값 추가
        // 우선 첫 값만 삽입
        int size_idx = 0;
        answer[size_idx]++;
        int max_num = end_time[size_idx];
        for (int i = 1; i < N; i++) {
            // 3. 가장 큰값보다 현재 값이 작거나 같으면 삽입
            if (end_time[i] <= max_num) {
                answer[size_idx]++;
            }
            // 4. 현재 값이 더 크다면 가장 큰 수 갱신
            else if (end_time[i] > max_num) {
                max_num = end_time[i];
                size_idx++;
                answer[size_idx]++;
            }
        }
        
        // 5. 정답 배열
        int[] res = new int[size_idx+1];
        for (int i = 0; i < size_idx+1; i++) {
            res[i] = answer[i];
        }
        
        System.out.println(size_idx);
        
        return res;
    }
}