강의

멘토링

로드맵

Inflearn brand logo image

인프런 커뮤니티 질문&답변

cherryjuice님의 프로필 이미지
cherryjuice

작성한 질문수

자바 코딩테스트 - it 대기업 유제

5. "cpu 스케쥴링" 코드 해설

cpu 스케줄링

작성

·

65

0

package chapter3.sol5_cpu_스케줄링;

import java.util.*;

public class Solution {
	public int[] solution(int[][] tasks) {
		int[] answer = new int[tasks.length];
		Queue<int[]> q = new PriorityQueue<>(Comparator.comparingInt((int[] a) -> a[1]).thenComparingInt(a -> a[0]));
		int[] ch = new int[tasks.length];

		for (int s = 0, i = 0; ; s++) {
			for (int j = 0; j < tasks.length; j++) {
				if (tasks[j][0] <= s && ch[j] == 0) {
					q.offer(new int[] {j, tasks[j][1]});
					ch[j] = 1;
				}
			}
			if (!q.isEmpty()) {
				int[] poll = q.poll();
				answer[i++] = poll[0];
				s += poll[1] - 1;
			}
			if (i == tasks.length)
				break;
		}
		return answer;
	}

	public static void main(String[] args) {
		Solution T = new Solution();
		System.out.println(Arrays.toString(T.solution(new int[][] {{2, 3}, {1, 2}, {8, 2}, {3, 1}, {10, 2}})));
		System.out.println(Arrays.toString(T.solution(new int[][] {{5, 2}, {7, 3}, {1, 3}, {1, 5}, {2, 2}, {1, 1}})));
		System.out.println(
			Arrays.toString(T.solution(new int[][] {{1, 2}, {2, 3}, {1, 3}, {3, 3}, {8, 2}, {1, 5}, {2, 2}, {1, 1}})));
		System.out.println(Arrays.toString(T.solution(new int[][] {{999, 1000}, {996, 1000}, {998, 1000}, {999, 7}})));
	}
}

안녕하세요 정답 코드가 아닌 이 코드도 가능한지 궁금합니다!

답변 2

1

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

만약 tasks의 길이가 100,000 이상이라면

위 코드에서 j for 문이 매번 100,000 이상인 tasks의 길이만큼 반복하는게 문제가 될 수 있습니다.

님의 코드는 시간복잡도가 O(n^2)이고, 영상의 방법은 시간복잡도가 O(nlogn)입니다.

0

안녕하세요, 인프런 AI 인턴입니다.

cherryjuice님께서 공유해주신 코드는 CPU 스케줄링 문제를 해결하기 위한 코드로, 각 작업이 제공된 시간에 실행 가능하고, 주어진 실행 시간 순서대로 처리되는 방식입니다. 해당 구현 방법은 우선순위 큐(PriorityQueue)를 활용하여, 실행 시간이 짧은 순서로 작업을 처리하게끔 작성되어 있습니다.

주어진 코드의 핵심은 다음과 같습니다:

  1. PriorityQueue를 사용하여 실행 시간이 빠른 작업을 우선 처리하도록 합니다.
  2. 각 작업이 도착하는 시점에 큐에 삽입되며, 처리 순서에 따라 answer 배열에 저장됩니다.
  3. 실행이 완료된 작업은 다시 순괄적 시간에서 제외되어 그 이후의 작업과 비교하지 않도록 처리가 이루어집니다.
  4. 큐가 비어있지 않을 때는 작업을 꺼내 처리하고, 시간이 그만큼 지나간다고 가정하여 다음 작업으로 넘어갑니다.

해당 코드 방식은 CPU 스케줄링 문제를 해결하는 일반적으로 사용되는 방법 중 하나로, 구현 자체는 정답 코드로써 사용될 수 있습니다. 그러나 실제로 요구되는 내용이나 제한 조건에 따라 다소 차이가 있을 수 있으며, 직접 실행해 보고 케이스에 알맞은 결과를 도출해 낼 수 있도록 검증하는 과정이 필요합니다.

더 많은 정보와 유사한 문제 해결 방법은 아래 URL을 참고해 주세요:

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

cherryjuice님의 프로필 이미지
cherryjuice

작성한 질문수

질문하기