문제
제출 코드(Java)
코드 제출
import java.util.*;
class Solution {
Queue<Job> queue = new PriorityQueue<>();
int total = 0;
int currentTime = 0;
int currentJobsIdx = 0;
public int solution(int[][] jobs) {
sort(jobs);
addFirstJob(jobs);
runJob();
while (isFinish(jobs)) {
addJob(jobs);
runJob();
}
return total / jobs.length;
}
private void sort(int[][] jobs){
Arrays.sort(jobs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
}
private boolean isFinish(int[][] jobs){
return currentJobsIdx < jobs.length || !queue.isEmpty();
}
private void addFirstJob(int[][] jobs) {
addJob(jobs);
if (queue.isEmpty()) {
currentTime++;
addFirstJob(jobs);
}
}
private void addJob(int[][] jobs) {
for (; currentJobsIdx < jobs.length; currentJobsIdx++) {
if (hasInputJob(jobs)) { inputJob(jobs); }
else { break; }
}
}
private void runJob(){
if ( queue.isEmpty() ) {
currentTime++;
return;
}
Job outputJob = queue.poll();
currentTime += outputJob.getRunningTime();
total += currentTime - outputJob.getInputTime();
}
private void inputJob(int[][] jobs){
Job inputJob = new Job().setInputTime(jobs[currentJobsIdx][0])
.setRunningTime(jobs[currentJobsIdx][1]);
queue.add(inputJob);
}
private boolean hasInputJob(int[][] jobs){
return jobs[currentJobsIdx][0] <= currentTime;
}
class Job implements Comparable<Job> {
private int inputTime;
private int runningTime;
public int getInputTime() {
return inputTime;
}
public Job setInputTime(int inputTime) {
this.inputTime = inputTime;
return this;
}
public int getRunningTime() {
return runningTime;
}
public Job setRunningTime(int runningTime) {
this.runningTime = runningTime;
return this;
}
@Override
public int compareTo(Job o) {
return this.getRunningTime() - o.getRunningTime();
}
}
}Class로 Job을 만들어 구현했는데, 나중에 생각해보니 굳이 Class를 사용안하고 Comparator로 사용해도 될 듯 싶다
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (4.42ms, 52.6MB)
테스트 2 〉 통과 (6.83ms, 53.9MB)
테스트 3 〉 통과 (3.95ms, 53.5MB)
테스트 4 〉 통과 (3.82ms, 52.7MB)
테스트 5 〉 통과 (3.90ms, 53.2MB)
테스트 6 〉 통과 (0.71ms, 52.2MB)
테스트 7 〉 통과 (2.98ms, 52.9MB)
테스트 8 〉 통과 (2.48ms, 52.4MB)
테스트 9 〉 통과 (1.43ms, 52.5MB)
테스트 10 〉 통과 (4.79ms, 53.3MB)
테스트 11 〉 통과 (0.77ms, 52.4MB)
테스트 12 〉 통과 (0.77ms, 52.5MB)
테스트 13 〉 통과 (0.71ms, 52.8MB)
테스트 14 〉 통과 (0.69ms, 51.8MB)
테스트 15 〉 통과 (0.73ms, 52.7MB)
테스트 16 〉 통과 (0.67ms, 52.6MB)
테스트 17 〉 통과 (0.62ms, 52.2MB)
테스트 18 〉 통과 (0.71ms, 52.5MB)
테스트 19 〉 통과 (0.74ms, 52.2MB)
테스트 20 〉 통과 (0.64ms, 53MB)제출 코드(Python)
첫번째 코드 제출
import heapq
def solution(jobs):
queue = []
jobs.sort(key=lambda x : x[0])
total = 0
currentJobIdx = 0
currentTime = 0
while currentJobIdx < len(jobs) or len(queue) > 0:
for i in range(currentJobIdx, len(jobs)):
if jobs[i][0] <= currentTime:
heapq.heappush(queue, jobs[i])
currentJobIdx += 1
else:
break
queue.sort(key=lambda x : x[1])
if len(queue) == 0:
currentTime += 1
continue
else:
job = heapq.heappop(queue)
currentTime += job[1]
total += (currentTime-job[0])
return total//len(jobs)heapq를 사용해 풀어낸 문제. lambda에 대한 이해도 필요
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (8.30ms, 10.3MB)
테스트 2 〉 통과 (7.15ms, 10.3MB)
테스트 3 〉 통과 (5.07ms, 10.4MB)
테스트 4 〉 통과 (5.62ms, 10.3MB)
테스트 5 〉 통과 (7.67ms, 10.3MB)
테스트 6 〉 통과 (0.10ms, 10.2MB)
테스트 7 〉 통과 (4.14ms, 10.3MB)
테스트 8 〉 통과 (2.93ms, 10.3MB)
테스트 9 〉 통과 (0.91ms, 10.2MB)
테스트 10 〉 통과 (8.81ms, 10.4MB)
테스트 11 〉 통과 (0.03ms, 10.2MB)
테스트 12 〉 통과 (0.04ms, 10.3MB)
테스트 13 〉 통과 (0.04ms, 10.3MB)
테스트 14 〉 통과 (0.03ms, 10.2MB)
테스트 15 〉 통과 (0.03ms, 10.2MB)
테스트 16 〉 통과 (0.02ms, 10.3MB)
테스트 17 〉 통과 (0.02ms, 10.3MB)
테스트 18 〉 통과 (0.02ms, 10.3MB)
테스트 19 〉 통과 (0.02ms, 10.3MB)
테스트 20 〉 통과 (0.01ms, 10.2MB)두번째 코드 제출
import heapq
from collections import deque
def solution(jobs):
tasks = deque(sorted([(x[1], x[0]) for x in jobs], key=lambda x: (x[1], x[0])))
q = []
heapq.heappush(q, tasks.popleft())
current_time, total_response_time = 0, 0
while len(q) > 0:
dur, arr = heapq.heappop(q)
current_time = max(current_time + dur, arr + dur)
total_response_time += current_time - arr
while len(tasks) > 0 and tasks[0][1] <= current_time:
heapq.heappush(q, tasks.popleft())
if len(tasks) > 0 and len(q) == 0:
heapq.heappush(q, tasks.popleft())
return total_response_time // len(jobs)정렬 기준을 수정하지 못하는 관계로 인덱스 순서를 변경하여 큐를 만들어 사용
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (1.07ms, 10.3MB)
테스트 2 〉 통과 (1.08ms, 10.3MB)
테스트 3 〉 통과 (0.84ms, 10.2MB)
테스트 4 〉 통과 (0.89ms, 10.3MB)
테스트 5 〉 통과 (1.10ms, 10.3MB)
테스트 6 〉 통과 (0.05ms, 10.3MB)
테스트 7 〉 통과 (0.82ms, 10.3MB)
테스트 8 〉 통과 (0.63ms, 10.3MB)
테스트 9 〉 통과 (0.21ms, 10.3MB)
테스트 10 〉 통과 (1.11ms, 10.5MB)
테스트 11 〉 통과 (0.02ms, 10.3MB)
테스트 12 〉 통과 (0.03ms, 10.3MB)
테스트 13 〉 통과 (0.03ms, 10.3MB)
테스트 14 〉 통과 (0.02ms, 10.2MB)
테스트 15 〉 통과 (0.02ms, 10.2MB)
테스트 16 〉 통과 (0.02ms, 10.2MB)
테스트 17 〉 통과 (0.02ms, 10.2MB)
테스트 18 〉 통과 (0.02ms, 10.2MB)
테스트 19 〉 통과 (0.02ms, 10.3MB)
테스트 20 〉 통과 (0.01ms, 10.2MB)매우 빠름...!
Be More!