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

※ 해당 문제의 링크는 여기입니다. ※

배열로 푸는 편이 더 코드가 단순해지지 않을까 생각하였지만

스택/큐 영역인 만큼 이 둘을 최대한 사용하는 것이 맞다고 생각이 들어

Queue를 사용하여 문제를 해결하였습니다.

 

코드와 알고리즘 로직을 설명하기 앞서

문제에서 주의 깊게 봐야 하는 점들을 먼저 설명하도록 하겠습니다.

제한 사항

1. 배포는 하루에 한 번만 가능하다.
2. 뒤에 있는 기능을 먼저 완성하였다고 바로 배포할 수 없고, 앞에 있는 기능이 완성된 후, 같이 배포하게 된다.
3. 한 번에 몇 개 배포하였는지 카운트를 배열에 저장한 후, 이를 반환해주어야 한다.

테스트 케이스 및 설명도 잘 되어있어 두세 번 정도 읽어보면 금방 이해할 수 있습니다.

알고리즘 로직

일단, 모든 알고리즘 해결 방식은 굉장히 많으므로 제가 문제를 해결한 방식의 알고리즘을 설명하도록 하겠습니다.

1. 총며칠이 흘렀는지 확인하는 변수 i 선언
2. Queue가 빌 때까지 무한 반복
3. 현재 첫 번째 인덱스 값 + (i * speeds [현재 인덱스])를 currentProgress로 저장. (이는 일종의 temp값으로 100 이상인지 아닌지를 묻는 데에 사용하게 됩니다.)
4. 앞에 기능이 수행되는 동안 뒤에 기능이 완료되었는지 확인하는 temp 변수
5. temp와 i 값 비교를 통해 확인
6. 동일하다면 arrayList에 set 메소드로 기존 값 + 1로 저장
7. 아니라면 그냥 add
8. 위 로직이 수행되었다면 Queue를 비우기 위해서 remove
9. Queue가 전부 비었다면 arrayList에 있는 값을 배열로 옮긴 뒤, 반환

전체 소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        // Queue 을 사용할 수 도 단순 배열로 처리할 수도 있음 (ArrayList 포함)
        Queue<Integer> progressQueue = new ArrayDeque<>();

        for (int progress : progresses) {
            progressQueue.add(progress);
        }

        ArrayList<Integer> list = new ArrayList<>();

        int i = 0, index = 0, resultIndex = -1; // index 는 값이 사라질때만 올라감
        while (!progressQueue.isEmpty()) {
            // 전부 빌 때 동안 계속 반복함
            int currentProgress = progressQueue.peek() + (i * speeds[index]);

            int temp = i;
            while (currentProgress < 100) {
                currentProgress += (speeds[index]);   // 현재 값(임의)에 speeds 값만큼 추가
                i++;
            }
            // 만일 100이 넘었다면, 삭제시킴
            index++;
            if (temp == i) {
                // 값이 바뀌지않았다면, 그냥 넣고
                list.set(resultIndex, list.get(resultIndex) + 1);
            }
            else {
                // 아니라면, resultIndex 값을 변동을 줘서 넣어야함
                list.add(++resultIndex, 1);
            }
            progressQueue.remove();
        }
        System.out.println(i);

        int[] result = new int[list.size()];
        for (int j = 0; j < list.size(); j++) {
            result[j] = list.get(j);
        }

        return result;
    }
}

스펙 및 결론

※제 기준이기때문에 다를 수 있습니다.※

사용된 시간: 0.4945 ms (1번 테스트 케이스 적용 시)

Hello, World! 만 출력한 코드 사용된 시간: 0.2745 ms

사람들이 자주 사용하는 소스에서 사용된 시간: 10.144799 ms (1번 테스트 케이스 적용 시)

import java.util.ArrayList;
import java.util.Arrays;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int[] dayOfend = new int[100];
        int day = -1;
        for(int i=0; i<progresses.length; i++) {
            while(progresses[i] + (day*speeds[i]) < 100) {
                day++;
            }
            dayOfend[day]++;
        }
        return Arrays.stream(dayOfend).filter(i -> i!=0).toArray();
    }
}

 

그래서 프로그래머스에 둘 다 해본 결과 Queue를 사용하는 편이

더 빠르고 메모리 할당을 덜 한다는 것을 확인하였습니다.

 

 

이상입니다.