💡 문제
챌린저: 디스크 컨트롤러 (
https://school.programmers.co.kr/learn/courses/30/lessons/42627
)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.
📝 선행 개념
힙(Heap) 이란
힙(Heap)은 완전 이진 트리의 일종으로, 특정한 조건을 만족하는 자료구조입니다. 힙은 다음 두 가지 유형이 있습니다
- 최대 힙(Max Heap): 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같은 힙. 따라서 루트 노드의 값이 가장 큽니다.
- 최소 힙(Min Heap): 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 힙. 따라서 루트 노드의 값이 가장 작습니다.
힙의 특성 덕분에 힙은 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다. 우선순위 큐는 요소를 삽입할 때 우선순위에 따라 정렬하고, 삭제할 때 가장 높은 우선순위 요소를 제거하는 큐입니다.
힙의 주요 특징:
- 완전 이진 트리: 힙은 완전 이진 트리 형태를 취합니다. 이는 트리의 모든 레벨이 채워져 있고 마지막 레벨은 왼쪽부터 차례대로 채워진다는 의미입니다.
- 힙 속성 유지: 최대 힙의 경우, 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같고, 최소 힙의 경우, 부모 노드의 값은 항상 자식 노드의 값보다 작거나 같습니다.
힙의 주요 연산:
- 삽입(Insertion): 새로운 요소를 힙에 추가합니다. 이때 힙 속성을 유지하기 위해 요소를 적절한 위치로 이동시킵니다.
- 삭제(Deletion): 일반적으로 루트 노드를 제거합니다. 루트 노드를 제거한 후 마지막 노드를 루트 위치로 이동시키고 힙 속성을 유지하기 위해 재정렬합니다.
- 힙 정렬(Heap Sort): 힙을 이용하여 배열을 정렬할 수 있습니다. 최대 힙을 사용하면 내림차순으로, 최소 힙을 사용하면 오름차순으로 정렬할 수 있습니다.
힙의 구현은 주로 배열을 사용합니다. 배열을 사용하면 부모 노드와 자식 노드의 인덱스를 쉽게 계산할 수 있습니다:
- 부모 노드 인덱스: parent(i) = (i - 1) / 2
- 왼쪽 자식 노드 인덱스: left(i) = 2 * i + 1
- 오른쪽 자식 노드 인덱스: right(i) = 2 * i + 2
다음은 Java에서 최소 힙을 사용하는 예제
import java.util.PriorityQueue;
public class MinHeapExample {
public static void main(String[] args) {
// PriorityQueue는 기본적으로 최소 힙으로 작동합니다.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 힙에 요소를 추가합니다.
minHeap.add(10);
minHeap.add(20);
minHeap.add(5);
minHeap.add(15);
// 힙에서 요소를 하나씩 제거하고 출력합니다.
while (!minHeap.isEmpty()) {
System.out.println(minHeap.poll()); // 5, 10, 15, 20 순으로 출력됩니다.
}
}
}
다음은 최대 힙 구현 (Java) 예제
Java의 PriorityQueue는 기본적으로 최소 힙으로 동작하므로, 최대 힙을 사용하려면 사용자 정의 비교자를 제공해야 합니다
import java.util.Collections;
import java.util.PriorityQueue;
public class MaxHeapExample {
public static void main(String[] args) {
// 최대 힙을 만들기 위해 Collections.reverseOrder()를 사용합니다.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 힙에 요소를 추가합니다.
maxHeap.add(10);
maxHeap.add(20);
maxHeap.add(5);
maxHeap.add(15);
// 힙에서 요소를 하나씩 제거하고 출력합니다.
while (!maxHeap.isEmpty()) {
System.out.println(maxHeap.poll()); // 20, 15, 10, 5 순으로 출력됩니다.
}
}
}힙은 효율적인 삽입과 삭제 연산이 필요한 상황에서 매우 유용한 자료구조입니다. 특히 우선순위 큐와 같은 응용에서 많이 사용됩니다.
🤓 문제 풀이
이 문제는 주어진 작업들의 요청부터 종료까지의 시간을 최소화하는 방법을 찾아야 합니다. 이를 위해 작업이 요청되는 시간과 소요 시간을 기준으로 작업을 처리하는 것이 중요합니다. 작업을 효율적으로 처리하기 위해 최소 힙(우선순위 큐)을 사용할 수 있습니다.
최소 힙을 사용하여 각 작업의 소요 시간이 짧은 작업을 먼저 처리하는 방식(SJF: Shortest Job First)을 구현할 수 있습니다. 이렇게 하면 평균 대기 시간을 최소화할 수 있습니다.
테스트 케이스
시험을 볼때는 IDE를 사용할 수 없는 회사가 있다는데 ㅠㅠ … 큰일이다 아직도 프로그래머스에 작성하는걸 못하겠다. 정처기 시험 때문에 수도코딩을 하기는 하지만.. 여전히 어렵다… (귀찮은걸까 ^_^,, 자동완성 최공,,)
public static void main(String[] args) {
Main sol = new Main();
// 테스트 케이스
int[][] jobs1 = {{0, 3}, {1, 9}, {2, 6}};
int result1 = sol.solution(jobs1);
System.out.println(result1); // 출력: 9
int[][] jobs2 = {{0, 10}, {2, 3}, {9, 3}};
int result2 = sol.solution(jobs2);
System.out.println(result2); // 출력: 9
}
문제1) 최소 힙 사용
public Class Main {
public int solution(int[][] jobs) {
// jobs 배열을 요청 시점을 기준으로 오름차순으로 정렬
Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
// 우선순위 큐를 사용하여 작업을 소요 시간 기준으로 정렬
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
int currentTime = 0; // 현재 시간
int totalWaitTime = 0; // 총 대기 시간
int jobIndex = 0; // jobs 배열을 순회하기 위한 인덱스
int jobCount = jobs.length; // 총 작업 수
// 모든 작업이 처리될 때까지 반복
while (jobIndex < jobCount || !pq.isEmpty()){
// 현재 시점에서 처리 가능한 모든 작업을 우선순위 큐에 추가
while (jobIndex < jobCount && jobs[jobIndex][0] <= currentTime){
pq.add(jobs[jobIndex++]);
}
if (pq.isEmpty()){
// 처리할 수 있는 작업이 없으면 현재 시간을 다음 작업의 요청 시간으로 업데이트
currentTime = jobs[jobIndex][0];
}else {
// 우선순위 큐에서 가장 짧은 작업을 꺼내서 처리
int[] currentJob = pq.poll();
currentTime += currentJob[1]; // 현재 시간에 작업 소요 시간을 더해 업데이트
totalWaitTime += currentTime - currentJob[0]; // 대기 시간 계산하여 총 대기 시간에 더함
}
}
// 평균 대기 시간을 계산하여 반환 (소수점 이하 버림)
return totalWaitTime / jobCount;
}
}!! 이 문제를 해결하기 위해 힙(PriorityQueue) 외에도 다른 접근 방법이 있습니다. 예를 들어, 단순하게 먼저 요청이 들어온 순서대로 처리하는 방법(FIFO 방식) 또는 단순히 배열을 사용하는 방법도 있습니다. 하지만 이러한 방법은 효율성이 떨어질 수 있습니다. 그래도 힙을 사용하지 않고 문제를 해결하는 방법을 살펴보겠습니다.
문제2) 단순 반복
단순 반복문을 사용하여 각 작업을 처리하는 방법입니다. 이 방법은 최적의 성능을 보장하지 않지만, 문제를 단순하게 해결
public Class Main {
public int solution(int[][] jobs) {
// 요청 시점 기준으로 정렬
Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
int currentTime = 0; // 현재 시간
int totalWaitTime = 0; // 총 대기 시간
int jobCount = jobs.length; // 작업의 총 개수
for (int i = 0; i < jobCount; i++) {
// 현재 시간이 요청 시점보다 작으면, 현재 시간을 요청 시점으로 맞춤
if (currentTime < jobs[i][0]) {
currentTime = jobs[i][0];
}
// 작업을 처리하고 현재 시간을 업데이트
currentTime += jobs[i][1];
// 대기 시간 계산
totalWaitTime += currentTime - jobs[i][0];
}
// 평균 대기 시간 계산 (소수점 이하 버림)
return totalWaitTime / jobCount;
}
}
문제3) 직접 구현한 우선순위 큐
우선순위 큐를 직접 구현하는 방법입니다. 이 방법은 좀 더 복잡하지만, 힙을 사용하지 않고도 최적의 작업 순서를 찾아낼 수 있습니다.
public Class Main {
public int solution(int[][] jobs) {
// 요청 시점 기준으로 정렬
Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
List<int[]> waitingQueue = new ArrayList<>();
int currentTime = 0; // 현재 시간
int totalWaitTime = 0; // 총 대기 시간
int jobIndex = 0; // jobs 배열의 인덱스
int jobCount = jobs.length; // 작업의 총 개수
while (jobIndex < jobCount || !waitingQueue.isEmpty()) {
// 현재 시점에서 처리 가능한 모든 작업을 대기 큐에 추가
while (jobIndex < jobCount && jobs[jobIndex][0] <= currentTime) {
waitingQueue.add(jobs[jobIndex++]);
}
if (waitingQueue.isEmpty()) {
// 처리할 수 있는 작업이 없으면 현재 시간을 다음 작업의 요청 시간으로 업데이트
currentTime = jobs[jobIndex][0];
} else {
// 대기 큐에서 가장 짧은 작업을 선택하여 처리
int[] shortestJob = Collections.min(waitingQueue, (a, b) -> a[1] - b[1]);
waitingQueue.remove(shortestJob);
currentTime += shortestJob[1]; // 현재 시간에 작업 소요 시간을 더해 업데이트
totalWaitTime += currentTime - shortestJob[0]; // 대기 시간 계산하여 총 대기 시간에 더함
}
}
// 평균 대기 시간을 계산하여 반환 (소수점 이하 버림)
return totalWaitTime / jobCount;
}
}결론
이러한 다양한 접근 방법이 있지만, 우선순위 큐를 사용한 힙 접근 방식이 최적의 성능을 보장하는 방법입니다. 이 문제에서는 우선순위 큐를 사용하는 것이 가장 효율적...
그냥 사람들이 다른 방식으로도 풀어보길래 작성해봄
📚 풀이 보완
코드 설명
1.정렬: 작업들을 요청 시간 기준으로 정렬합니다. 이는 첫 번째 요청을 처리하기 위해 필요합니다.
- jobs 배열을 요청 시점을 기준으로 오름차순으로 정렬합니다.
- 이는 처음 작업을 처리하기 위해 요청 순서대로 작업을 큐에 넣기 위함입니다.
Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
2. 우선순위 큐: 작업의 소요 시간을 기준으로 최소 힙(우선순위 큐)을 사용하여 작업을 관리합니다.
- PriorityQueue를 사용하여 작업의 소요 시간 기준으로 작업을 정렬합니다.
- 이는 가장 짧은 작업을 먼저 처리하기 위해 사용합니다.
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
3. 시간 관리: 현재 시간과 대기 시간, 작업 인덱스를 초기화합니다.
4. 작업 처리 루프: 모든 작업이 처리될 때까지 반복합니다.
- 모든 작업이 처리될 때까지 반복합니다.
- 현재 시점에서 처리 가능한 모든 작업을 우선순위 큐에 추가합니다.
- 처리 가능한 작업이 없으면 현재 시간을 다음 작업의 요청 시간으로 업데이트합니다.
- 우선순위 큐에서 가장 짧은 작업을 꺼내서 처리합니다.
5. 평균 시간 계산: 모든 작업의 총 대기 시간을 작업 수로 나눠서 평균을 구합니다.
- 모든 작업의 총 대기 시간을 작업 수로 나눠서 평균을 구합니다.
- 소수점 이하는 버립니다.
📍 Plus+
1. PriorityQueue<int[]> pq = new PriorityQueue<>() 사용 방법과 예제
자바에서 제공하는 우선순위 큐입니다. 기본적으로 자연 순서(자연스럽게 정렬 가능한 객체의 경우) 또는 사용자 정의 비교기(Comparator)를 사용하여 큐의 헤드 요소를 유지합니다. **PriorityQueue<int[]>**의 경우 배열을 요소로 가지는 우선순위 큐를 만듭니다.
기본 생성자로 우선순위 큐를 생성하면 요소들이 자연 순서(Comparable 인터페이스를 구현한 객체)로 정렬됩니다. 하지만 배열의 경우는 Comparable을 구현하지 않으므로 기본 생성자는 적합하지 않습니다. 배열을 정렬하려면 Comparator를 제공해야 합니다.
import java.util.PriorityQueue;
import java.util.Arrays;
public class PriorityQueueExample {
public static void main(String[] args) {
// 기본 생성자를 사용한 PriorityQueue
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 요소 추가
pq.add(3);
pq.add(1);
pq.add(2);
// 요소 출력
while (!pq.isEmpty()) {
System.out.println(pq.poll()); // 출력: 1 2 3
}
// 배열을 요소로 가지는 PriorityQueue (오류 발생)
// PriorityQueue<int[]> pqArray = new PriorityQueue<>(); // 오류: int[]는 Comparable을 구현하지 않음
// Comparator를 사용한 PriorityQueue
PriorityQueue<int[]> pqArray = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pqArray.add(new int[]{3, 2});
pqArray.add(new int[]{1, 5});
pqArray.add(new int[]{2, 3});
while (!pqArray.isEmpty()) {
int[] element = pqArray.poll();
System.out.println(Arrays.toString(element)); // 출력: [1, 5] [2, 3] [3, 2]
}
}
}2. Comparator 설명
Comparator는 자바에서 객체를 비교하기 위한 인터페이스입니다. Comparator를 사용하여 특정 기준에 따라 두 객체의 순서를 정의할 수 있습니다. Comparator는 두 메서드를 제공합니다:
- compare(T o1, T o2): 두 객체 o1과o2를 비교하고, 첫 번째가 두 번째보다 작으면 음수, 같으면 0, 크면 양수를 반환합니다.
- reversed(): 기존 비교기를 반대로 변환합니다.
comparingInt은 Comparator 인터페이스의 정적 메서드로, int 값에 대한 비교기를 생성합니다. 이 메서드는 람다식을 인수로 받아 람다식이 반환하는 int 값으로 비교를 수행합니다.
3. Comparator.comparingInt(a -> a[1]) 설명
Comparator.comparingInt(a -> a[1])는 int 배열 a의 두 번째 요소(a[1])를 기준으로 비교하는 Comparator를 생성합니다. 이 비교기는 PriorityQueue에서 요소를 정렬할 때 사용됩니다.
- a -> a[1]: 람다 표현식으로, 배열 **a**의 두 번째 요소를 반환합니다.
- Comparator.comparingInt: int 값을 기준으로 비교하는 **Comparator**를 생성합니다.
이 조합은 배열의 두 번째 요소를 기준으로 요소를 비교하고 정렬하는 데 사용됩니다.
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Arrays;
public class DiskController {
public int solution(int[][] jobs) {
Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
int currentTime = 0;
int totalWaitTime = 0;
int jobIndex = 0;
int jobCount = jobs.length;
while (jobIndex < jobCount || !pq.isEmpty()) {
while (jobIndex < jobCount && jobs[jobIndex][0] <= currentTime) {
pq.add(jobs[jobIndex++]);
}
if (pq.isEmpty()) {
currentTime = jobs[jobIndex][0];
} else {
int[] job = pq.poll();
currentTime += job[1];
totalWaitTime += currentTime - job[0];
}
}
return totalWaitTime / jobCount;
}
public static void main(String[] args) {
DiskController sol = new DiskController();
int[][] jobs1 = {{0, 3}, {1, 9}, {2, 6}};
int result1 = sol.solution(jobs1);
System.out.println(result1); // 출력: 9
int[][] jobs2 = {{0, 10}, {2, 3}, {9, 3}};
int result2 = sol.solution(jobs2);
System.out.println(result2); // 출력: 9
int[][] jobs3 = {{1, 2}, {2, 1}, {3, 2}};
int result3 = sol.solution(jobs3);
System.out.println(result3); // 출력: 3
}
}
'Algorithm > 코딩테스트' 카테고리의 다른 글
| [리트코드][JAVA] 2551. Put Marbles in Bags (구슬을 가방에 담다) (0) | 2024.05.26 |
|---|---|
| [프로그래머스][JAVA] 이중 우선순위 큐 (0) | 2024.05.26 |
| [프로그래머스][JAVA] 주식 가격 (0) | 2024.05.23 |
| [프로그래머스][JAVA] 다리를 지나는 트럭 (0) | 2024.05.23 |
| [백준][JAVA] 비슷한 단어 (0) | 2024.05.22 |