Programming/Programmers
[프로그래머스] 선입 선출 스케줄링(Python)
데이터현 2022. 1. 31. 17:19
//programmers.co.kr/learn/courses/30/lessons/12920
코딩테스트 연습 - 선입 선출 스케줄링
처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다. 이 CPU는 다음과 같은 특징이 있습니다. CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니
programmers.co.kr
이진탐색을 활용해야 하는 문제였다.
비슷한 문제를 풀었었는데 떠올리지 못했다.
def solution(n,cores): if n <= len(cores): return n n -= len(cores) left = 1 right = max(cores)*n while left < right: mid = (left+right)//2 work = 0 for core in cores: work += mid//core if work >= n: right = mid else: left = mid + 1 for core in cores: n -= (right-1)//core for i in range(len(cores)): if right % cores[i] == 0: n -= 1 if n == 0: return i + 1문제 링크 : programmers.co.kr/learn/courses/30/lessons/12920
코딩테스트 연습 - 선입 선출 스케줄링
처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다. 이 CPU는 다음과 같은 특징이 있습니다. CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니
programmers.co.kr
접근 과정
1) 우선순위 큐와 반복문을 활용한 풀이
- 우선순위 큐를 이용하여 core들을 순회시켰다.
- 반복문안에서 core들이 순서대로 작업을 1개씩 담당하며 처리했고 n은 차감되었다.
- n이 0이 되었을 때, 마지막 작업을 처리한 core의 인덱스를 출력하였다.
=> 정확성은 통과하였으나, 효율성에서 시간초과라는 결과를 보였다.
2) 시간이 Time일 때, 처리한 작업을 구하는 Count함수와 구할 시간을 찾는 이분탐색을 활용
- 시간이 time일 때, 그 시간까지 처리한 작업의 수량을 리턴하는 CountWork 함수를 구현하였다.
- 초기 min = 0, max = (core[0]*n)으로 두고 이분탐색을 진행하였다.
- 처음으로 n이상의 작업을 처리한 시간 time을 탐색하였다.
- time까지 처리한 작업량과 n의 차이와 time에 작업을 처리한 core의 index를 비교하여 n을 처리하는 core의 인덱스를 출력하였다.
=> 정확성과 효율성 모두 통과
소스 코드 및 결과
Code 1 : 우선순위 큐와 반복문을 활용
public static int solution(int n, int[] cores) { int answer = 0; if (n <= cores.length) { // n이 core의 개수보다 작을 경우 n번째 코어를 리턴 return n; } n -= cores.length; // 시간이 0일 때, 모든 코어가 작업을 하나씩 담당하여 처리 // 다음 처리시간순으로 정렬, 처리시간이 같을 경우는 index값이 작은 순으로 정렬 PriorityQueue<core> pq = new PriorityQueue<>((q1, q2) -> { if (q1.time == q2.time) { return q1.index - q2.index; } return q1.time - q2.time; }); for (int i = 0; i < cores.length; i++) { // core를 pq에 삽입 pq.add(new core(i, cores[i])); } int time = 1; while (n > 0) { // n이 0이 될 때까지 core가 작업을 하나씩 담당 처리 core now = pq.poll(); // 다음 작업을 처리할 core if (now.time == time) { // 현재시간과 core의 다음처리시간이 같은 경우 n--; } else if (now.time > time) { // 현재시간보다 core의 다음처리가 큰 경우 time = now.time; n--; } if (n == 0) { // 작업이 모두 처리되었으니, core의 인덱스를 출력 answer = now.index + 1; } else { // 작업이 남은경우, 사용한 core의 다음 처리시간을 구하여 pq에 삽입 pq.add(new core(now.index, time + cores[now.index])); } } return answer; } } class core { int index; int time; public core(int index, int time) { this.index = index; this.time = time; } }결과 :
Code 2 : 이분탐색을 활용
public static int solution(int n, int[] cores) { int answer = 0; int min = 0; // 시간의 최소값 int max = cores[0]*n; // 시간의 최대값 int time = 0; int m = 0; // time까지 처리한 작업량 while (min <= max) { int mid = (min+max)/2; int count = CountWork(mid, cores); if (count >= n) { // 해당시간까지 처리한 작업량보다 n이 크면 time과 m갱신 max = mid-1; time = mid; m = count; }else{ min = mid+1; } } m-=n; // 처리한 작업량과 n의 차이 갱신 for(int i = cores.length-1; i>=0; i--){ if (time % cores[i] == 0) { // 시간이 time일때, 작업을 처리하는 core if (m == 0) { answer = i+1; break; } m--; } } return answer; } static int CountWork(int time, int[] cores){ if (time == 0) { // 시간이 0일 때, 처리할 수 있는 작업량은 코어의 개수 return cores.length; } int count = cores.length; // 시간이 0일 때, 처리한 작업량 for(int i = 0; i<cores.length; i++){ // time까지 코어가 처리할 수 있는 작업량 합산 count += (time/cores[i]); } return count; } }결과 :