프로그래머스-기능개발

목차

1.문제

2.문제 풀이 과정

3.타인의 코드 분석

 

1.문제

 

 

 

2.문제 풀이 과정

2-1. 문제의 요구사항

• 각 기능이 있는데 해당 기능의 진도가 100%가 될 때 서비스에 반영이 가능
• 뒤의 기능이 먼저 완성이 되어도, 앞의 기능이 완료가 될 때까지는 배포를 할 수 가 없다는 점
• 앞의 기능이 배포될 때 , 이미 완료가 된 뒤의 기능도 같이 배포를 한다는 점 
• 각 배포시점에 배포되는 기은의 개수를 순서대로 배열로 반환을 한다.
• 문제의 제한사항의 경우에는 
  • progressess와 speeds 배열의 길이는 1이상 100이하
  • 각 작업의 개발 속도는 1이상 100이하의 자연수
  • 각 작업의 진도는 1이상 100이하의 자연수
  • 배포의 경우에는 하루에 한번만 가능하고, 하루의 끝에 이루어진다.

2-2. 문제 풀이에 관한 분석

 

우선 이 문제에서 가장 중요하다고 생각을 한 부분은 각 기능이 완료되기까지 필요한 정확한 일수를 계산을 하는 것입니다. 왜냐하면 배포의 우선순위와 묶음의 경우에도 결국에는 "각 작업이 며칠안에 끝나는가?" 라는 완료 날짜가 기준이 되어야하기 때문입니다. 그래서 순서대로 생각을 해보면 아래와 같습니다.

 

1.기능 완료 일수에 관한 로직을 계산

 

기능 완료 일수에 대한 로직을 계산을 하는 식은 아래와 같습니다. 

 

기능개발 완료 일수 = (100- 진도율)/ 속도 

 

하지만 이대로만 하는 경우에는 소수점 처리를 하는데 있어서 문제가 발생을 할 수 있으니. 나머지가 조금이라도 있다면 작업이 하루 더 걸리는 것으로 판단을 해서 올림처리를 하는 방식을 생각했습니다.

 

2. 큐를 사용( 순차적 처리를 위해서)

 

다음으로 이문제를 해결하기 위한 방식으로는 큐를 생각을 했습니다. 큐를 선택한 이유는 문제에서 요구사항중에서  "뒤의 기능이 먼저 완성이 되어도, 앞의 기능이 완료가 될 때까지는 배포를 할 수 가 없다는 점" 을 보았을때 앞선 작업이 완료가 되어어야 뒤의 작업이 배포가 될 수 있기에 계산된 완료 일수를 큐에 순서대로 넣어서 처리를 하는 것이 맞다고 판단을 해서 큐룰 선택을 했습니다.

 

3. 배포 묶음의 기준

 

앞의 작업이 완료되는 날짜를 기준으로, 그 이후에 완료가 되는 작업들은 배포 시점에서 작업과 같거나 늦어지기에 같은 묶음으로 묶어서 처리를 해보는게 어떨지를 고민해 봤습니다.

 

2-3. 문제 의사 코드

 

위의 과정을 토대로 해서 생각해낸 제 의사코드는 아래와 같습니다.

 

• 작업진행배열을 반복문으로 돌려서 각 기능별 완료까지 걸리는 일수를 계산을 해서 큐에 넣기.
  • 일수 = (100 - 현재 진도) / 속도
  • 나머지가 존재를 하면 올림 처리를 해서 하루 추가하기.
• 큐에 남는게 없을때까지 while문을 돌리기
  • 큐에서 첫번째 기능의 완료 일수를 꺼내서 기준값으로 삼는다.
  • 큐에 다음 기능이 기준값보다 작거나 같으면 완료된 것으로 간주를 하고 카운트를 증가를 한다.
  • 큐의 다음 기능이 기준값보다 큰경우에는 지금까지의 카운트를 결과를 내놓을 리스트에 담고 기준값을 새 기능의 완료일수로 갱신을한다.
• 마지막으로 최종 리스트에 남은 카운트를 추가를 하고, 결과를 배열로 변환을 해서 리턴을 한다.

이렇게 생각을 하고 정답을 제출한 제코드는 아래와 같습니다. 

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer>queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        int[] answer = {};
        
        //1.개발 진척도를 계산 
        for(int i = 0 ; i< progresses.length; i++) {
        	// 진척도가 맞아 떨어지는 경우에는 그대로 식을 적용해서 큐에 저장
            if(100-progresses[i] % speeds[i] == 0) {
                queue.offer((100-progresses[i]) / speeds[i]);
            } else {
            // 나머지가 있는 경우에는 하루 더 걸리는 것이므로 올림처리를 한다.
                queue.offer(((100 - progresses[i]) / speeds[i]) + 1);
            }
        }
        // 2.큐에 들어간 내용을 꺼내기 전에 비어있는지를 확인 
        // 비어있으면 0으로 리턴
        if(queue.isEmpty()) {
            return new int[]{0};
        }
        // 3.큐에 현재 들어가있는 작업의 완료 일수를 뽑아 기준으로 설정하기.
        int curr = queue.poll();
        int count  = 1; 
        
        // 시뮬레이션 시작
        while(!queue.isEmpty()) {
        	// 4. 앞선 작업보다 일찍 끝나면
            if(curr >= queue.peek()) {
            	// 카운트(묶음 개수)를 올리고 같이 배포
                count++;
                // 처리된 작업을 제거
                queue.poll();
            } else {
            	// 5.앞선 작업보다 늦게 끝나는 경우에는 현재까지의 묶음을 저장하고
                list.add(count);
                //새 묶음을 시작
                count = 1;
                // 기준을 변경을 한다.
                curr = queue.poll();
            }
        }
        
        // 마지막으로 남은 묶음을 저장 
        list.add(count);
        
        //최종적으로 리스트를 스트림을 사용해서 배열로 변환
        answer = list.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }
}

 

3.타인의 코드 분석

 

이 문제를 풀고 난 다음에 다른 사람들이 어떻게 문제를 풀었는지를 보았다. 코드는 대부분 대동소이했다. 큐를 활용해서 앞선 작업이 완료될 때까지 뒤의 작업들이 완료되어 대기하고 있다면 묶어서 한 번에 배포를 하는 로직으로 구현을 했습니다. 그 외에도 큐가 아닌 리스트를 활용해서 푼 방법이 있어서 봤습니다.

 

리스트를 활용한 방식

 

 

 

 

 

구현 방식

 

각 작업의 완료 일수를 미리 계산하여 ArrayList에 저장.

리스트의 첫 요소(j)를 기준으로 삼고, 다음 요소들을 비교하며 deployDay[j] < deployDay[k]인 지점까지 묶음(count++).

• 장점
  • 데이터가 한 번 정제(필요 일수 계산)된 상태에서 연산하므로 큐와 거의 동일하게 효율적임.
  • get(index) 접근이 가능하여 로직 구현이 상대적으로 유연함.
• 단점 
  • 큐의 'FIFO(꺼내면 사라짐)' 특성을 인위적으로 구현해야 함(인덱스 이동 등).