https://programmers.co.kr/learn/courses/30/lessons/42586

소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int[] solution(int[] progresses, int[] speeds) {
    int start = 0;
    List<Integer> list = new ArrayList<Integer>();
    while (start != progresses.length) {
        int deploy = 0;
        for (int i = start; i < progresses.length; i++) {
            progresses[i] += speeds[i];
        }

        for (int i = start; i < progresses.length; i++) {
            if (progresses[start] < 100) {
                break;
            }

            if (progresses[i] >= 100) {
                ++start;
                ++deploy;
            }
        }

        if (deploy != 0) {
            list.add(deploy);
        }
    }

    int[] answer = list.stream().mapToInt(i -> i).toArray();
    return answer;
}

흐름

  1. 기능개발이 완료된 인덱스부터 반복하기 위해 start 변수 생성

  2. 기능개발이 끝날 때 까지 반복

  3. 개발이 안 끝난 기능 index 부터 돌면서 작업 속도를 더 함

  4. 개발이 안 끝난 기능 index 부터 돌면서 첫 번째 기능이 개발 됐는지 확인하고 안 끝났으면 3 번으로 돌아감

  5. 첫 번째 기능이 완료 되었으면 그 다음 기능개발을 위해 ++start 하고, deploy된 기능을 카운팅하는 deploy 변수를 증가

  6. deploy한 기능이 있는 경우에만 list에 저장

  7. ArrayList를 int[]로 변경

  8. 끝

다른 분의 소스

1
2
3
4
5
6
7
8
9
10
11
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();
}

로직

  • 기능 갯수 만큼 돌면서 진도율과 날짜 * 개발 속도를 비교해서 100 보다 작으면 다음날로 증가시키고 크면 그 날짜에 저장되는 갯수를 증가시킴

  • 대박

결과

1 번

번호 속도
테스트 1 통과 (4.53ms, 50.8MB)
테스트 2 통과 (5.07ms, 50.6MB)
테스트 3 통과 (5.09ms, 52.8MB)
테스트 4 통과 (5.29ms, 52.4MB)
테스트 5 통과 (8.36ms, 55MB)
테스트 6 통과 (4.95ms, 51.2MB)
테스트 7 통과 (5.58ms, 52.6MB)
테스트 8 통과 (5.18ms, 50.7MB)
테스트 9 통과 (5.44ms, 52.5MB)
테스트 10 통과 (5.22ms, 50.5MB)

2 번

번호 속도
테스트 1 통과 (6.60ms, 51.4MB)
테스트 2 통과 (6.83ms, 53.1MB)
테스트 3 통과 (6.92ms, 52.5MB)
테스트 4 통과 (6.70ms, 52.8MB)
테스트 5 통과 (19.88ms, 52.4MB)
테스트 6 통과 (5.05ms, 50.7MB)
테스트 7 통과 (7.01ms, 52.5MB)
테스트 8 통과 (4.68ms, 50.5MB)
테스트 9 통과 (6.95ms, 52.2MB)
테스트 10 통과 (5.31ms, 50.8MB)
  • 두 소스 모두 Arrays.stream을 사용하지 않고 반복해서 저장하면 1초 대로 줄어듬.
  • 확실히 스트림이 느린 듯함.

테스트 케이스

1
2
3
assertArrayEquals(new int[] {2,1}, test.solution(new int[] {93, 30, 55}, new int[] {1, 30, 5}));
assertArrayEquals(new int[] {3}, test.solution(new int[] {0, 30, 55}, new int[] {1, 99, 99}));
assertArrayEquals(new int[] {1,1,1}, test.solution(new int[] {3, 2, 1}, new int[] {1, 1, 1}));

전체 소스

https://github.com/jungguji/algorithm_training/blob/master/src/main/java/algorithm/programmers/level2/stackqueue/%EB%8B%A4%EB%A6%AC%EB%A5%BC_%EC%A7%80%EB%82%98%EB%8A%94_%ED%8A%B8%EB%9F%AD.java