프로그래머스 문제 풀이/프로그래머스 (JAVA)

JAVA 프로그래머스 Lv.3 디스크 컨트롤러

gamja00 2024. 9. 20. 20:09

 

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

 

문제

  1. 각 작업에 대한 [작업 요청 시첨, 작업 소요 시간]이 2차원 배열로 입력됨.
  2. 각 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 최소화한 방법을 이용해 가장 작은 평균을 출력.

 

 

초기 코드

import java.util.PriorityQueue;

class Request implements Comparable<Request> {
        private int number;
        private int time;

        public Request(int number, int time) {
            this.number = number;
            this.time = time;
        }

        @Override
        public int compareTo(Request r) {
            if (this.time > r.time)
                return 1;
            else if (this.time < r.time)
                return -1;
            return 0;
        }
    }

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int num = 0;
        
          PriorityQueue<Request> list = new PriorityQueue<>();

        for (int i = 0; i < jobs.length; i++) {
            list.add(new Request(jobs[i][0], jobs[i][1]));
        }

        for (int i = 0; i < jobs.length; i++) {
            Request temp = list.remove();
            if (i == 0) {
                num += temp.time + temp.number;
            } else {
                num += temp.time + jobs.length - temp.number;
            }
            answer += num;
            num -= jobs.length - temp.number;
        }
        
        return answer / jobs.length;
    }
}

 

 

추가한 클래스가... 인식?이 안 되는 것 같다...

만들긴 했는데 어떻게 쓰는 건질 모름...

 

찾아봤음

 

수정한 코드

import java.util.PriorityQueue;


class Solution {
    public int solution(int[][] jobs) {
        class Request implements Comparable<Request> {
        private int number;
        private int time;

        public Request(int number, int time) {
            this.number = number;
            this.time = time;
        }

        @Override
        public int compareTo(Request r) {
            if (this.time > r.time)
                return 1;
            else if (this.time < r.time)
                return -1;
            return 0;
        }
    }
        int answer = 0;
        int num = 0;
        
          PriorityQueue<Request> list = new PriorityQueue<>();

        for (int i = 0; i < jobs.length; i++) {
            list.add(new Request(jobs[i][0], jobs[i][1]));
        }

        for (int i = 0; i < jobs.length; i++) {
            Request temp = list.remove();
            if (i == 0) {
                num += temp.time + temp.number;
            } else {
                num += temp.time + jobs.length - temp.number;
            }
            answer += num;
            num -= jobs.length - temp.number;
        }
        
        return answer / jobs.length;
    }
}

이렇게 넣으면 된다고 합니다.

근데 정확도 10점이어서 다시 풀어야 됩니다...

 

작업 시간이 짦은 순서대로만 정렬해서 그런 것 같습니다.

요청 시간도 이용해야 될 것 같으니 다시 수정하겠습니다.

 

수정한 코드

import java.util.PriorityQueue;
import java.util.Comparator;

class Job {
        int number;
        int time;

        public Job(int number, int time) {
            this.number = number;
            this.time = time;
        }
    }
class Solution {
    
    public int solution(int[][] jobs) {
        int answer = 0;
        int num = 0;
        int end = 0;
        int count = 0;


        PriorityQueue<Job> request = new PriorityQueue<>(Comparator.comparingInt(o -> o.time));
        PriorityQueue<Job> sequence = new PriorityQueue<>(Comparator.comparingInt(o -> o.number));

        for (int i = 0; i < jobs.length; i++) {
            sequence.add(new Job(jobs[i][0], jobs[i][1]));
        }

        end = sequence.peek().time;

        while (count < jobs.length) {
            if (request.isEmpty()) {
                while (!sequence.isEmpty() && sequence.peek().number <= end) {
                    request.add(sequence.poll());
                }
            }

            Job temp = request.poll();

            if (count == 0) {
                num += temp.time + temp.number;
            } else {
                num += end - temp.number + temp.time;
            }

            count++;
            answer += num;
            num -= end - temp.number;

            if (request.isEmpty()) {
                end = num;
            }
        }
        
        return answer / jobs.length;
    }
}

근데 얘도 정확성... 10입니다...

에효

 

질문에 있는 테스트케이스 예시 보고 수정한 코드

import java.util.PriorityQueue;
import java.util.Comparator;

class Job {
        int number;
        int time;

        public Job(int number, int time) {
            this.number = number;
            this.time = time;
        }
    }
class Solution {
    
    public int solution(int[][] jobs) {
        int answer = 0;
        int num = 0;
        int end = 0;
        int count = 0;
        int length = 0;

        PriorityQueue<Job> sequence = new PriorityQueue<>(Comparator.comparingInt(o -> o.number));
        PriorityQueue<Job> request = new PriorityQueue<>(Comparator.comparingInt(o -> o.time));

        for (int i = 0; i < jobs.length; i++) {
            sequence.add(new Job(jobs[i][0], jobs[i][1]));
        }

        end = sequence.peek().time;

        while (count < jobs.length) {
            if (request.isEmpty()) {
                while (!sequence.isEmpty() && sequence.peek().number <= end) {
                    request.add(sequence.poll());
                }
            }

            Job temp = request.poll();

            if (count == 0) {
                num += temp.time + temp.number;
            } else {
                num += end - temp.number + temp.time;
            }

            count++;
            answer += num;
            length += temp.time;
            num -= end - temp.number;

            if (!request.isEmpty() && !sequence.isEmpty()
                    && length + sequence.peek().time
                    <= num + end - request.peek().number + request.peek().time) {
                num += end - sequence.peek().number + sequence.peek().time;
                answer += sequence.peek().number +sequence.peek().time;
                sequence.poll();
                count++;
            }

            if (request.isEmpty()) {
                end = num;
            }
        }
        
        return answer / jobs.length;
    }
}

 

근데 얘도 결과가 똑같습니다...

뭐 어쩌라는 건지 모르겠습니다...

 

다시 수정한 코드

import java.util.PriorityQueue;
import java.util.Comparator;

class Job {
        int number;
        int time;

        public Job(int number, int time) {
            this.number = number;
            this.time = time;
        }
    }
class Solution {
    
    public int solution(int[][] jobs) {
        int answer = 0;
        int count = 0;

        PriorityQueue<Job> sequence = new PriorityQueue<>(Comparator.comparingInt(o -> o.number));
        PriorityQueue<Job> request = new PriorityQueue<>(Comparator.comparingInt(o -> o.time));

         for (int i = 0; i < jobs.length; i++) {
            sequence.add(new Job(jobs[i][0], jobs[i][1]));
        }

        int end = sequence.peek().time;

        while (count < jobs.length) {
            while (!sequence.isEmpty() && sequence.peek().number <= end) {
                request.add(sequence.poll());
            }

            if (!request.isEmpty()) {
                Job temp = request.poll();
                answer += end - temp.number + temp.time;
                end = temp.time;
                count++;
                if (request.isEmpty()) {
                    end = temp.number;
                }
            }
        }
        
        return answer / jobs.length;
    }
}

 

시간초과가 많이 나고 실패도 몇 개 있어서 정확도 0.

0점

0점입니다

 

https://velog.io/@davidko/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%94%94%EC%8A%A4%ED%81%AC-%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%ACjava

 

참고한 블로그입니다.

이분은 잘하셨는데 저는 왜 안 될까요.

 

최종 코드

import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Arrays;

class Job {
        int number;
        int time;

        public Job(int number, int time) {
            this.number = number;
            this.time = time;
        }
    }
class Solution {
    
    public int solution(int[][] jobs) {
        int answer = 0;
        int count = 0;
        int index = 0;
        int end = 0;

        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        PriorityQueue<Job> request = new PriorityQueue<>(Comparator.comparingInt(o -> o.time));


        while (count < jobs.length) {
            while (index < jobs.length && jobs[index][0] <= end) {
                request.add(new Job(jobs[index][0], jobs[index][1]));
                index++;
            }

            if (request.isEmpty()) {
                end = jobs[index][0];
            } else {
                Job temp = request.poll();
                answer += end - temp.number + temp.time;
                end += temp.time;
                count++;
            }

        }
        
        return answer / jobs.length;
    }
}

 

마지막에 만들었던 코드에서 수정해서 완성했다.

첨부한 블로그와 거의 비슷한 코드가 된 것 같다.

원래 PriorityQueue를 두 개 사용했는데 그렇게 쓰면 기존의 배열을 정렬한 채로 사용할 수가 없어서 큐 하나를 제거하고 입력된 배열을 정렬하여 사용하기로 하였다.

while 반복문에서 if 부분을 두 번 거치는 것이 무리를 주는 것 같아 배열을 사용하여 temp를 이용하여 end를 정하지 않도록 하여 시간을 줄였다.

 

 

백준보다 문제가 어려운 것 같다.

백준보다 레벨이 세세하게 나눠지지 않아서 그런 것 같다.

어렵다.