문제

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progresses	speeds	return
[93, 30, 55]	[1, 30, 5]	[2, 1]
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

입출력 예 설명

입출력 예 #1

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.

두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.

세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2

모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

※ 공지 - 2020년 7월 14일 테스트케이스가 추가되었습니다.

문제접근

1️⃣ 문제풀이

• 문제 상황: 주어진 작업의 현재 진도(progresses)와 각 작업의 하루 개발 속도(speeds)가 주어지고, 각 작업이 완료되어 서비스에 반영될 수 있는 시점을 구하는 것입니다. 작업 진도가 100%에 도달했을 때, 해당 작업은 서비스에 반영가능하다.
• 조건: 뒤에 있는 작업이 먼저 개발될 수 있지만, 앞선 작업이 배포되기 전까지는 배포될 수 없습니다. 즉, 작업은 주어진 순서대로 배포되어야 합니다.
• 목표: 각 작업이 완료되는 데 필요한 일수를 계산하고, 일정 기간에 몇 개의 작업이 배포될 수 있는지를 결정하는 것입니다.
• 예시:
  • 작업 진도가 93, 개발 속도가 1인 작업은 7일이 걸린다.
  • 작업 진도가 30, 개발 속도가 30인 작업은 3일이 걸린다.
  • 작업 진도가 55, 개발 속도가 5인 작업은 9일이 걸린다.
  • 결과적으로, 3일에 완료된 작업은 7일째에 앞선 작업과 함께 배포되고, 9일째에는 마지막 작업이 배포됩니다. 따라서, 7일째에는 2개의 작업이, 9일째에는 1개의 작업이 배포됩니다.
• 해결 방법: 작업이 완료되는 데 필요한 일수를 계산하여 큐에 저장하고, 큐를 사용하여 배포 일정을 결정합니다.

2️⃣ 현재 진도와 개발 속도 받아오기

   public static void main(String[] args) {
        Solution T = new Solution();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int [] progress = new int[n];
        int [] speeds = new int[n];

        for (int i = 0; i < progress.length; i++) {
            progress[i] = sc.nextInt();
        }

        for (int i = 0; i < speeds.length; i++) {
            speeds[i] = sc.nextInt();
        }
        System.out.println(Arrays.toString(T.solution(progress, speeds)));
    }

   public int[] solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> list = new ArrayList<>();//기능 수 저장
        Queue<Integer> queue = new LinkedList<>();//작업일 수 저장

ArrayList<Integer>list는 각 배포마다 완료되는 기능의 수를 저장한다.

Queue<Integer>queue는 각 기능이 완료되는데 필요한 일수를 저장한다.

큐(Queue)

선입선출(FIFO : First in First Out의 성격을 가졌다) Queue<자료형> 변수명 = new LinkedList<>();

Queue 메서드

Operation	Description
삽입 (add)	q.add(삽입할 value): 삽입 성공 시 true / 실패 시 Exception 발생
삽입 (offer)	q.offer(삽입할 value): 삽입 성공 시 true / 실패 시 false 반환
삭제 (remove)	q.remove(): 삭제된 value 반환 / 공백 큐이면 Exception("NoSuchElementException") 발생
삭제 (remove with value)	q.remove(삭제할 value): 해당 value 존재 시 삭제 후 true 반환 / 존재하지 않으면 false 반환
삭제 (poll)	q.poll(): 삭제된 value 반환 / 공백 큐이면 null 반환
front value 반환 (element)	q.element(): 큐 head에 위치한 value 반환 / 공백 큐이면 Exception("NoSuchElementException") 발생
front value 반환 (peek)	q.peek(): 큐 head에 위치한 value 반환 / 공백 큐이면 null 반환
큐 초기화 (clear)	q.clear(): 큐 초기화 (반환 값 없음)
큐 크기 (size)	q.size(): 큐의 크기 반환
원소 존재 여부 (contains)	q.contains(찾을 value): 해당 값 존재 시 true 반환 / 없을 때 false 반환
공백 큐 여부 (isEmpty)	q.isEmpty(): 공백 큐이면 true 반환 / 아니면 false 반환

3️⃣ 작업 완료 시간 계산

 for (int i = 0; i < progresses.length; i++) {
            if ((100 - progresses[i]) % speeds[i] == 0) {
                queue.add((100 - progresses[i]) / speeds[i]);
            } else {
                queue.add((100 - progresses[i] + speeds[i] - 1) / speeds[i]);
            }
        }

작업완료시간 = (100일 - 현재작업일) % 소요시간 이 완전히 나눠질때

100이 초과되지 않고 “딱 맞아 떨어지는 경우”

 queue.add((100 - progresses[i]) / speeds[i]);

100이 초과되는 경우

 queue.add((100 - progresses[i] + (speeds[i] - 1)) / speeds[i]);

예를 들어 progress[i]=100, speeds[i]=2일 경우

➡️ 남은 작업량 7%를 하루 개발 속도 2%로 나누면 3.5 가된다.

그러나 일자로 따지자면 3.5일은 없으니, 나머지가 있을 경우 -1 해주어, 하루를 추가해줘야한다.

4️⃣ 배포일자 계산

 while (!queue.isEmpty()) {
            int current = queue.poll();
            int count = 1;
            while (!queue.isEmpty() && current >= queue.peek()) {
                count++;
                queue.poll();
            }
            list.add(count);
        }

• while루프를 사용해 queue 가 비어있지 않을 동안은 계속 처리를 진행해준다.
  • int current = queue.poll(); → 큐에서 첫번째 기능의 완료일수를 가지고 온다.
  • int count = 1; → 배포에 포함될 기능의 수를 카운트 한다.

 while (!queue.isEmpty() && current >= queue.peek()) {
                count++;
                queue.poll();
            }

• while (!queue.isEmpty() && current >= queue.peek()): 이 루프는 큐가 비어있지 않고, 현재 기능(current)의 완료 일수보다 다음 기능의 완료 일수가 작거나 같을 때까지 계속 진행
  • current >= queue.peek(): 큐의 다음 기능(peek)의 완료 일수가 현재 기능의 완료 일수보다 작거나 같으면, 이 기능도 현재 배포에 포함됩니다.
• count++: 동일 배포일에 포함되는 기능의 수를 증가시킵니다.
• queue.poll(): 동일 배포일에 포함되는 기능을 큐에서 제거합니다.

배포일 계산 결과 저장:

• list.add(count): 현재 배포일에 완료되는 기능의 수(count)를 결과 리스트에 추가합니다.

코드

import java.util.*;

public class Solution {//기능 개발

    public int[] solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> list = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();//작업일 수 저장

        //작업완료 시간 계산
        for (int i = 0; i < progresses.length; i++) {
            if ((100 - progresses[i]) % speeds[i] == 0) {
                queue.add((100 - progresses[i]) / speeds[i]);
            } else {
                queue.add((100 - progresses[i] + (speeds[i] - 1)) / speeds[i]);
            }
        }
				//배포일수 계산
        while (!queue.isEmpty()) {
            int current = queue.poll();
            int count = 1;
            while (!queue.isEmpty() && current >= queue.peek()) {
                count++;
                queue.poll();
            }
            list.add(count);
        }

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

    public static void main(String[] args) {
        Solution T = new Solution();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int [] progress = new int[n];
        int [] speeds = new int[n];

        for (int i = 0; i < progress.length; i++) {
            progress[i] = sc.nextInt();
        }

        for (int i = 0; i < speeds.length; i++) {
            speeds[i] = sc.nextInt();
        }
        System.out.println(Arrays.toString(T.solution(progress, speeds)));
    }
}

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int solution(int[] priorities, int location) {
        // 우선순위 큐 선언(내림 차순)
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        int answer = 0;

        // 우선순위 큐에 우선순위 요소 추가
        for (int i : priorities) {
            queue.offer(i);
        }

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            // 기존 우선순위 배열 순회
            for (int i = 0; i < priorities.length; i++) {
                // 현재 작업의 위치 찾기
                if (queue.peek() == priorities[i]) {
                    queue.poll();
                    answer++;

                    // 현재 작업이 location과 같으면 answer 반환
                    if (location == i) {
                        return answer;
                    }
                }
            }
        }

        return answer;
    }
}

초기코드