프로그래머스 디스크 컨트롤러(lvl3) 풀어보기

문제링크

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

프로그래머스

---

문제 핵심

 우선순위 디스크 컨트롤러는 다음과 같이 동작합니다.

 

1. 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있습니다. 처음에 이 큐는 비어있습니다.
2. 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높습니다.
3. 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행합니다.
4. 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킵니다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있습니다. 이 과정에서 걸리는 시간은 없다고 가정합니다.

각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 정수 배열 jobs가 매개변수로 주어질 때, 우선순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수부분을 return 하는 solution 함수를 작성해 주세요.

---

알고리즘

-

1.문제 우선순위에 맞게 정렬하는 큐를 생성

2.중복방지위해 큐에들어간 번호를 담는 맵생성

3.현재시간보다 작거나같은 작업 큐와중복맵에담기

4.만약 담을게없으면 그냥 시간 보내기

5. 담은게 있다면 처리하기

-대기시간/처리시간 구해서 answer에 더하기

-시간은 처리시간만큼만 증가하기

---

코드

public static int solution(int[][] jobs) {

        int answer = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {

            // 1순위: 소요시간이 짧은 것

            if (a[1] != b[1]) {

                return Integer.compare(a[1], b[1]);

            }

            // 2순위: 요청시간이 빠른 것

            if (a[0] != b[0]) {

                return Integer.compare(a[0], b[0]);

            }

            // 3순위: 작업번호가 작은 것

            return Integer.compare(a[2], b[2]);

        });

        int nowT = 0;

        int[][] fine = new int[jobs.length][3];

        Map<Integer, Boolean> added = new HashMap<>();

        int fineIndex = 0;

        while (fineIndex < jobs.length) {

            for (int i = 0; i < jobs.length; i++) {

                if (nowT >= jobs[i][0] && !added.containsKey(i)) {

                    added.put(i, true);

                    pq.add(new int[] { jobs[i][0], jobs[i][1], i });

                }

            }

            if (pq.isEmpty()) {

                nowT += 1;

            } else {

                int[] job = pq.poll();

                fine[fineIndex] = job;

                fineIndex += 1;

                int wait=nowT-job[0]; // 대기시간

                answer=answer+job[1]+wait;// 처리시간 + 대기시간

                nowT += job[1];

            }

        }

        System.out.println(Arrays.deepToString(fine));

        System.out.println(answer);

        answer=answer/jobs.length;

        System.out.println(answer);

        return answer;

    }

 

---

결과

---

gpt피드백

1. 알고리즘 평가

특히 잘한 부분은 PriorityQueue를 단순히 쓰는 데서 끝난 게 아니라 직접 다중 우선순위를 구성한 거야.

알고리즘상 아쉬운 부분

가장 큰 건 이 부분이야.

while (fineIndex < jobs.length) {

    for (int i = 0; i < jobs.length; i++) {
        if (nowT >= jobs[i][0] && !added.containsKey(i)) {

작업을 하나 처리할 때마다 jobs 전체를 처음부터 다시 확인해.

작업이 N개라면 대략:

N개 작업 처리
×
매번 최대 N개 탐색

→ O(N²)

이번 문제에서는 실제로 통과했으므로 충분히 허용되는 성능이었지만, 더 좋은 알고리즘으로 만들 수 있어.

2. 코드 평가

평가

코드 자체는 의도가 상당히 잘 보이는 편이야.

코드 개선점

알고리즘은 그대로 유지하면서 코드만 개선한다면 이렇게 볼 수 있어.

HashMap → boolean[]

answer 계산 단순화

현재:

int wait = nowT - job[0];
answer += job[1] + wait;
nowT += job[1];

원리를 이해했으니 이제는:

nowT += job[1];
answer += nowT - job[0];

으로 줄일 수 있어.

둘은 완전히 같은 계산이야.

---

후기

-아진짜 너무 헷갈리는문제였다
노는시간/대기시간/처리시간을 각각각

구별해야헀는데 노는시간 대기시간을 같이생각해서

헤맸고 애초에 문제를 제대로 안읽어서 다른쪽으로 코드를짰던

낭패를 맛봤던 문제다 그래도 포기하지 않고 풀어서 다행이다