5-2 기능 개발

유태형·2022년 5월 26일

Java 알고리즘 프로그래머스

알고리즘 - Java

목록 보기

12/32

출처

해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다.

문제

문제 분석

작업별 걸리는 날짜를 구하고 남은 작업들중 맨앞의 작업이 완성될때 몇개가 같이 완성되는지(맨앞의 작업보다 걸리는 일수가 적은 연속된 일든은 몇개인지)구하는 문제입니다. 현재 작업이 완성 되었더라도 이전의 작업이 완성되어야 완료할 수 있으므로 Queue 자료구조를 이용하는 것이 적절해 보입니다.

풀이

몇일 걸리는지, 또 작업들의 몇개가 한번에 되는지 구하기 위해서는

progresses와 speeds를 기반으로 남은 날짜를 구해야 합니다.
맨앞의 작업이 완성될때 같이 완성되어 있을 작업의 갯수를 구하기

progresses와 speeds를 기반으로 남은 날짜를 구해야 합니다.

나의 풀이

		int[] days = new int[progresses.length]; //작업 시간을 담는 배열
        for(int i=0;i<days.length;i++) //남은 작업 시간 계산
            days[i] = (int)Math.ceil((100 - (double)progresses[i]) / (double)speeds[i]);
        //queue : 남은 작업 시간을 담는 큐, list : 각 배포마다 몇개의 기능 배포
        Queue<Integer> queue = Arrays.stream(days).boxed().collect(Collectors.toCollection(LinkedList::new));

강의의 풀이

		Queue<Integer> queue = new LinkedList<>();
        for(int i=0;i<progresses.length;i++){
            float p = progresses[i];
            float s = speeds[i];
            int days = (int)Math.ceil((100 - p) / s);
            queue.offer(days);
        }

남은 날짜 = (100 - 진행도) / 속도로 100% 완성되기 까지 대략 몇일 정도 남았는지 계산할 수 있을 것입니다.

맨앞의 작업이 완성될때 같이 완성되어 있을 작업의 갯수를 구하기

맨앞의 작업이 완성될때 같이 완성되어 있을 작업의 갯수를 구하기 위해 맨 앞요소보다 걸리는 시간이 적은 2번재,3번째,....가 몇개인지 구해야 합니다.

나의 풀이

		while(!queue.isEmpty()){
            int day = queue.peek(); //현재 작업이 걸리는 시간
            int task = 0; //현재 작업을 완료하는 동안 끝난 뒷 작업들
            while(!queue.isEmpty() && day >= queue.peek()){ //큐가 비지 않고 현재 작업 시간보다 적게 걸리는 작업들
                task++; //추가
                queue.poll(); //제거하고 다음 작업
            }
            list.add(task); //작업의 갯수를 리스트에 추가
        }

강의의 풀이

		Queue<Integer> answer = new LinkedList<>();
        int d = queue.poll();
        int count = 1;
        while(!queue.isEmpty()){
            int n = queue.poll();
            if(d >= n){
                count ++;
                continue;
            }
            answer.offer(count);
            count = 1;
            d = n;
        }
        
        answer.offer(count);

저는 이중 while문으로 현재의 맨앞 요소로부터 몇개가 남은 일수가 더 작은지 계산하기 위해 while문을 한번 더 실행하였고, 강의의 경우 하나의 while문으로 순차적으로 갯수를 세알렸습니다.

소스 코드

	public int[] solution(int[] progresses, int[] speeds) {
        //5 10 1 1 20 1 , 5
        //10 1 1 20 1, 5
        //10 1 1 20 1, 10
        //20 1, 10
        //20 1, 20
        // , 20

        int[] days = new int[progresses.length]; //작업 시간을 담는 배열
        for(int i=0;i<days.length;i++) //남은 작업 시간 계산
            days[i] = (int)Math.ceil((100 - (double)progresses[i]) / (double)speeds[i]);
        //queue : 남은 작업 시간을 담는 큐, list : 각 배포마다 몇개의 기능 배포
        Queue<Integer> queue = Arrays.stream(days).boxed().collect(Collectors.toCollection(LinkedList::new));
        List<Integer> list = new ArrayList<>();
        //큐가 빌 때 까지
        while(!queue.isEmpty()){
            int day = queue.peek(); //현재 작업이 걸리는 시간
            int task = 0; //현재 작업을 완료하는 동안 끝난 뒷 작업들
            while(!queue.isEmpty() && day >= queue.peek()){ //큐가 비지 않고 현재 작업 시간보다 적게 걸리는 작업들
                task++; //추가
                queue.poll(); //제거하고 다음 작업
            }
            list.add(task); //작업의 갯수를 리스트에 추가
        }
        return list.stream().mapToInt(i->i).toArray(); //리스트를 배열로 반환
    }