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

---

 

✏️ Solution 1

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class 기능개발 {

    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> q = new LinkedList<>();
        Map<Integer,Integer> map = new LinkedHashMap<>();

        for (int i=0; i<progresses.length; i++) {
            q.add(progresses[i]);
        }
        System.out.println(q);

        int n = 1;
        for (int i=0; i<progresses.length; i++) {
            while (true) {
                if (progresses[i] + speeds[i]*n >= 100) {
                    q.poll();
                    map.put(n, map.getOrDefault(n, 0)+1);
                    System.out.printf("q: %s, map: %s \n", q, map);
                    break;
                } else {
                    n++;
                }
            }
        }
        System.out.println(map.values());

        return map.values().stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        기능개발 s = new 기능개발();
        System.out.println(Arrays.toString(s.solution(new int[] {93, 30, 55}, new int[] {1, 30, 5})));
        System.out.println();
        System.out.println(Arrays.toString(s.solution(new int[] {95, 90, 99, 99, 80, 99}, new int[] {1, 1, 1, 1, 1, 1})));
    }
}

 

Map<Integer,Integer> map = new LinkedHashMap<>();

map :  n일째에 몇개 배포되었는지 담는다

 

map.values().stream().mapToInt(Integer::intValue).toArray()

Map의 값들을 int 배열로 바꾸는 코드

 

map.values()
Map에서 값들만(Collection) 가져온다

Map<Integer, Integer> map = Map.of(1, 3, 2, 5);
map.values(); // [3, 5]

 

.stream()
Collection을 Stream으로 바꾼다
Stream을 쓰면 반복/필터링/변환 등을 함수형 스타일로 작성 가능하다

.mapToInt(Integer::intValue)
Stream<Integer>를 IntStream으로 변환한다

Integer::intValue

Integer 객체 → int 값으로 변환하는 메서드 참조    ⬇️

Integer i = 5;
int j = i.intValue(); // 언박싱

 

.toArray()
IntStream을 int[] 배열로 변환한다 

 

출력결과

[93, 30, 55]
q: [30, 55], map: {7=1} 
q: [55], map: {7=2} 
q: [], map: {7=2, 9=1} 
[2, 1]
[2, 1]

[95, 90, 99, 99, 80, 99]
q: [90, 99, 99, 80, 99], map: {5=1} 
q: [99, 99, 80, 99], map: {5=1, 10=1} 
q: [99, 80, 99], map: {5=1, 10=2} 
q: [80, 99], map: {5=1, 10=3} 
q: [99], map: {5=1, 10=3, 20=1} 
q: [], map: {5=1, 10=3, 20=2} 
[1, 3, 2]
[1, 3, 2]

---

 

✏️ Solution 2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 기능개발_2 {

    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> result = new ArrayList<>();
        int n = progresses.length;
        int[] days = new int[n];

        // 각 작업마다 걸리는 날짜 계산
        for (int i=0; i<n; i++) {
            days[i] = (int) Math.ceil( (100.0-progresses[i]) / speeds[i]);
        }
        System.out.println("각 작업마다 걸리는 날짜: " + Arrays.toString(days));

        // 앞에 있는 작업보다 늦게 끝나면 따로 배포, 아니면 같은 날 배포
        int cnt = 1;
        int prev = days[0];
        for (int i=1; i<n; i++) {
            if (days[i] <= prev) {
                cnt++;
            } else {
                result.add(cnt);
                cnt = 1;
                prev = days[i];
            }
            System.out.printf("prev:  %s,  cnt: %d,  result: %s \n", prev, cnt, result);
        }
        result.add(cnt);
        System.out.println(result);
        
        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        기능개발_2 s = new 기능개발_2();
        System.out.println(Arrays.toString(s.solution(new int[] {93, 30, 55}, new int[] {1, 30, 5})));
        System.out.println();
        System.out.println(Arrays.toString(s.solution(new int[] {95, 90, 99, 99, 80, 99}, new int[] {1, 1, 1, 1, 1, 1})));
    }
}

 

- 각 기능이 며칠 뒤에 배포 가능한지 계산

- 앞 기능이 완료될 때 같이 배포될 수 있는 뒷 기능들을 묶는다

 

prev :  현재 배포 기준 날짜

days[i] <= prev :  같이 배포 가능하다면  cnt++

더 늦게 끝나는 작업이 있다면  =>  지금까지 모은 cnt를 result에 저장하고 새 그룹 시작

 

 

출력 결과

각 작업마다 걸리는 날짜: [7, 3, 9]
prev:  7,  cnt: 2,  result: []
prev:  9,  cnt: 1,  result: [2]
[2, 1]
[2, 1]

각 작업마다 걸리는 날짜: [5, 10, 1, 1, 20, 1]
prev:  10,  cnt: 1,  result: [1]
prev:  10,  cnt: 2,  result: [1]
prev:  10,  cnt: 3,  result: [1]
prev:  20,  cnt: 1,  result: [1, 3]
prev:  20,  cnt: 2,  result: [1, 3]
[1, 3, 2]
[1, 3, 2]

---

 

Solution1 의 시간 복잡도는 거의 O(n^2) 이다

Queue와 Map을 함께 사용 → 메모리 사용이 약간 많다

이전 작업이 완료될 때까지 n을 증가시키는 while루프는 비효율적일 수 있다

 

Solution2 의 시간 복잡도는 O(n)

List<Integer> 하나만 사용 → 더 효율적이다

 

꼭 Queue 자료구조가 아니더라도 해결 가능하다.