[프로그래머스] 기능개발 - Java [자바]

 

📜 문제 내용

 

 

🤔 과정

• 간단한 수식을 통해 작업 수행 기간만을 뽑아내야겠다고 판단. 
• 선순위의 기능이 개발 완료 되어야만 후순위도 같이 배포되므로, FIFO 특징의 queue를 이용해 peek 으로 비교하고, poll 으로 꺼내버리는 방법이 적절하다고 판단. 

 

✨ 최초 제출 답안

• 제출 시 테스트케이스 중 절반이 틀림. 반드시 내 코드 수정할 것. 

 

• 수정 답안

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
		
        // 작업 기간을 담을 queue 생성
        Queue<Integer> qDuration = new LinkedList<>();
        for (int i = 0; i < progresses.length; i++) {
            int duration = (100 - progresses[i]) / speeds[i];
            int rest = (100 - progresses[i]) % speeds[i];
			
            // 나누어떨어지면 그대로 삽입, 아니면 1일 추가 
            if (rest != 0) {
                qDuration.offer(duration + 1);
            } else {
                qDuration.offer(duration);
            }
        }
		
        // 작업 기간 전부를 이어붙일 문자열 
        String cntGroup = "";

        while (!qDuration.isEmpty()) {
            int curr = qDuration.poll();
            int serviceCnt = 1;
		
        	// queue가 비어있지 않고, 현재 작업 기간보다 다음 작업 기간이 짧으면
            // 작업 기간 추가 및 poll
            while (!qDuration.isEmpty() && curr >= qDuration.peek()) {
                serviceCnt++;
                qDuration.poll();
            }

            cntGroup += serviceCnt + " ";
            System.out.println(cntGroup);
        }
		
        // 작업 개발일을 띄어쓰기로 split 
        String[] cntGroupArr = cntGroup.split(" ");
        int len = cntGroupArr.length;

        int[] answer = new int[len];

        for (int i = 0; i < len; i++) {
            answer[i] = Integer.parseInt(cntGroupArr[i]);
        }

        return answer;
    }
}

 

• 통과하지 못한 이유는 반례가 아니라, 문자열 때문이었다. 바보 같이 모든 작업기간이 한 자리 수라고 생각하고 "" 으로 split 했는데, 그 이상이 될 수 있으므로 처음부터 띄어쓰기를 포함해 붙이고 " "로 split한 결과 모두 통과가 되었다. 

좌) 문자열 붙이기로 구현한 내 코드 답안, 우) arrayList를 따로 생성해 구현한 일부 참고한 코드 답안

• ArrayList를 하나 만들면 그만큼 비용이 크게 들 줄 알고 문자열 자르기로 구현했는데, 막상 결과를 보니 문자열이 더 느렸고, 메모리는 비슷했다. 

이유)
1. 문자열 연결 연산이 많이 발생하면 시간과 메모리 사용이 비효율이게 된다. 
2. ArrayList는 동적 배열로, 동적 크기 조절로 인해 필요한 만큼만 메모리를 사용하므로 효율적이다.
3. ArrayList의 요소 추가 연산은 상수 시간 내에 이루어지는 반면, 문자열 연결은 새로운 문자열을 만들어야 하므로 시간이 더 걸리게 된다. 

 

✍️ 재제출 답안

import java.util.*;
import java.io.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        
        // 최종 답안을 잠시 넣을 tmp 
        ArrayList<Integer> tmp = new ArrayList<>();
        
        // 기능마다의 작업 수행 기간을 담을 queue
        Queue<Integer> qDuration = new LinkedList<>();
        for(int i=0;i<progresses.length;i++){
            int duration = (100 - progresses[i]) / speeds[i];
            int rest = (100 - progresses[i]) % speeds[i];
            
            // 나누어떨어지지 않으면 1일 추가 
            if(rest != 0){
                qDuration.add(duration + 1);
            }else{
                qDuration.add(duration);
            }
        }
        
        // 배포마다의 기능 갯수
        int serviceCnt = 1;
        int curr = qDuration.poll();

        while(!qDuration.isEmpty()){
            if(curr >= qDuration.peek()){
                serviceCnt++;
                qDuration.poll();
            }else{
                tmp.add(serviceCnt);
                serviceCnt = 1;
                curr = qDuration.poll();
            }
        }
        tmp.add(serviceCnt); // 마지막 서비스 갯수 추가 

        int[] answer = new int[tmp.size()];
        for(int i=0;i<answer.length;i++){
            answer[i] = tmp.get(i);
        }

        return answer;
    }
}

 

• 결국 queue를 poll, peek 하는 부분을 다른 사람의 풀이를 참고해 해결했다. 
• 문제 풀이 과정은 어렵지 않은데, 내 코드에서 어떤 반례 때문에 통과가 안 됐는 지 너무 답답했고, 반드시 내 코드를 수정해서 반례를 찾아봐야겠다. 

 

🔗 문제 링크

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

프로그래머스