JUINTINATION
프로그래머스 코딩테스트 고득점 Kit - 힙(더 맵게, 디스크 컨트롤러, 이중우선순위큐) 본문
프로그래머스 코딩테스트 고득점 Kit - 힙(더 맵게, 디스크 컨트롤러, 이중우선순위큐)
DEOKJAE KWON 2024. 12. 17. 20:411번 문제: 더 맵게
https://school.programmers.co.kr/learn/courses/30/lessons/42626
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만든다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해야 한다.
접근
모든 음식의 스코빌 지수가 K 이상인지 확인하기 위해 작은 수를 갖는 원소가 우선순위가 높은 우선순위큐를 사용한다. 반복문을 순회하며 우선순위큐의 맨 앞에 있는 원소의 스코빌 지수가 K 이상이라면 그 뒤에 있는 모든 원소는 그 이상이므로 모든 원소를 순회하며 K 와 비교할 필요가 없다.
코드
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
PriorityQueue<Integer> pQueue = new PriorityQueue<>();
for (int e : scoville) {
pQueue.offer(e);
}
int answer = 0;
while (pQueue.size() >= 2 && pQueue.peek() < K) {
pQueue.offer(pQueue.poll() + 2 * pQueue.poll());
answer++;
}
if (pQueue.size() == 1) {
if (pQueue.poll() < K) {
answer = -1;
}
} else if (pQueue.isEmpty()) {
answer = -1;
}
return answer;
}
}while문에서 pQueue.size() >= 2를 확인하는 이유는 2개의 음식을 섞어야 하는데 남아있는 음식이 그보다 작으면 섞을 수 없기 때문이다.
또한 모든 음식의 스코빌 지수가 이미 K 이상이라면 섞는 의미가 없기 때문에 while문에 들어가기 전에 확인해야 한다.
2번 문제: 디스크 컨트롤러
https://school.programmers.co.kr/learn/courses/30/lessons/42627
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
이 문제에서는 우선순위 디스크 컨트롤러라는 가상의 장치를 이용한다고 가정하며, 이는 다음과 같이 동작한다.
- 어떤 작업 요청이 들어왔을 때 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 있다. 처음에 이 큐는 비어있다.
- 디스크 컨트롤러는 하드디스크가 작업을 하고 있지 않고 대기 큐가 비어있지 않다면 가장 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킨다. 이때, 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것 순으로 우선순위가 높다.
- 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행한다.
- 하드디스크가 어떤 작업을 마치는 시점과 다른 작업 요청이 들어오는 시점이 겹친다면 하드디스크가 작업을 마치자마자 디스크 컨트롤러는 요청이 들어온 작업을 대기 큐에 저장한 뒤 우선순위가 높은 작업을 대기 큐에서 꺼내서 하드디스크에 그 작업을 시킨다. 또, 하드디스크가 어떤 작업을 마치는 시점에 다른 작업이 들어오지 않더라도 그 작업을 마치자마자 또 다른 작업을 시작할 수 있다. 이 과정에서 걸리는 시간은 없다고 가정한다.
예를 들어
- 0ms 시점에 3ms가 소요되는 0번 작업 요청
- 1ms 시점에 9ms가 소요되는 1번 작업 요청
- 3ms 시점에 5ms가 소요되는 2번 작업 요청와 같은 요청이 들어왔을 때 이를 그림으로 표현하면 다음과 같다.
이 요청을 우선순위 디스크 컨트롤러가 처리하는 과정은 다음 표와 같습니다.
| 시점 | 하드디스크 | 대기 큐 | 디스크 컨트롤러 |
| 0ms | [] | ||
| 0ms | [[0번, 0ms, 3ms]] | 0번 작업 요청을 대기 큐에 저장 | |
| 0ms | 0번 작업 시작 | [] | 대기 큐에서 우선순위가 높은 0번 작업을 꺼내서 작업을 시킴 |
| 1ms | 0번 작업 중 | [[1번, 1ms, 9ms]] | 1번 작업 요청을 대기 큐에 저장 |
| 3ms | 0번 작업 완료 | ||
| 3ms | [[1번, 1ms, 9ms], [2번, 3ms, 5ms]] | 2번 작업 요청을 대기 큐에 저장 | |
| 3ms | 2번 작업 시작 | [[1번, 1ms, 9ms]] | 대기 큐에서 우선순위가 높은 2번 작업을 꺼내서 작업을 시킴 |
| 8ms | 2번 작업 완료 | [[1번, 1ms, 9ms]] | |
| 8ms | 1번 작업 시작 | [] | 대기 큐에서 우선순위가 높은 1번 작업을 꺼내서 작업을 시킴 |
| 17ms | 1번 작업 완료 | [] |
모든 요청 작업을 마쳤을 때 각 작업에 대한 반환 시간(turnaround time)은 작업 요청부터 종료까지 걸린 시간으로 정의할 때, 위의 우선순위 디스크 컨트롤러가 처리한 각 작업의 반환 시간은 다음 그림, 표와 같다.
| 작업 번호 | 요청 시각 | 작업 종료 시각 | 반환 시간 |
| 0번 | 0ms | 3ms | 3ms(= 3ms - 0ms) |
| 1번 | 1ms | 17ms | 16ms(= 17ms - 1ms) |
| 2번 | 3ms | 8ms | 5ms(= 8ms - 3ms) |
우선순위 디스크 컨트롤러에서 모든 요청 작업의 반환 시간의 평균은 8ms(= (3ms + 16ms + 5ms) / 3)가 된다.
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 정수 배열 jobs 가 매개변수로 주어질 때, 우선순위 디스크 컨트롤러가 이 작업을 처리했을 때 모든 요청 작업의 반환 시간의 평균의 정수부분을 return 하는 solution 함수를 작성해야 한다.
접근
먼저 작업 번호, 요청되는 시점, 소요시간을 갖는 Process 클래스를 만들고, 대기 큐의 규칙에 맞도록 Comparable<T>를 구현하여 compareTo(T o)를 오버라이딩한다. 또한 jobs 배열은 요청 시각의 오름차순으로 정렬되어 있다는 보장이 없기 때문에 반복문 안에서 모든 jobs 배열을 순회하며 현재 시각에 맞게 대기 큐에 삽입하는 과정을 거쳐야 한다.
jobs 배열을 요청 시각에 맞게 정렬한 뒤에 진행할 수도 있지만 일단은 위와 같은 방법을 사용하고, 추후에 더 좋은 아이디어가 떠오르면 추가해보도록 하겠다.
코드
import java.util.*;
class Process implements Comparable<Process> {
private int num, request, time;
public Process(int num, int request, int time) {
this.num = num;
this.request = request;
this.time = time;
}
public int getRequest() {
return request;
}
public int getTime() {
return time;
}
@Override
public int compareTo(Process o) {
if (o.time == this.time) {
if (o.request == this.request) {
return this.num - o.num;
} else {
return this.request - o.request;
}
} else {
return this.time - o.time;
}
}
}
class Solution {
public int solution(int[][] jobs) {
PriorityQueue<Process> readyQueue = new PriorityQueue<>();
int answer = 0, time = 0;
while (true) {
for (int i = 0; i < jobs.length; i++) {
int[] job = jobs[i];
if (job[0] <= time) {
readyQueue.add(new Process(i, job[0], job[1]));
job[0] = Integer.MAX_VALUE;
}
}
if (!readyQueue.isEmpty()) {
Process p = readyQueue.poll();
time += p.getTime();
answer += time - p.getRequest();
} else {
time++;
}
if (readyQueue.isEmpty()) {
boolean isEnd = true;
for (int[] job : jobs) {
if (job[0] != Integer.MAX_VALUE) {
isEnd = false;
break;
}
}
if (isEnd) break;
}
}
return answer / jobs.length;
}
}while문 안에서 현재 시각(ms)을 의미하는 time이 점점 늘어난다.
while문 안의 첫 번째 for문에서 job은 i번 작업인 jobs[i]이며, job의 요청 시각(ms)을 의미하는 job[0]가 time보다 작거나 같으면 readyQueue에 들어간다. 그 의미로 job[0]을 Integer.MAX_VALUE로 변경한다.
그 아래의 if문에서 readyQueue에 들어있는 하나의 작업을 poll하고, 하드디스크는 한 번에 하나의 작업만 할 수 있으므로 time에 poll된 작업의 소요 시간을 더한다. 그리고 마지막에 return할 answer에 time에서 poll된 작업의 요청 시각을 뺀 값을 더한다. 이때 readyQueue가 비어있다면 1ms가 지났다는 의미로 time에 1을 더한다.
위의 작업을 반복하다가 마지막에 readyQueue가 비어있고, 모든 작업이 readyQueue에 비어있었다면(= 모든 job[0]가 Integer.MAX_VALUE라면) while문을 종료하고, answer / jobs.length를 반환한다.
3번 문제: 이중우선순위큐
https://school.programmers.co.kr/learn/courses/30/lessons/42628
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
풀이
이 문제에서의 이중우선순위큐는 다음 연산을 할 수 있는 자료구조이다.
| 명령어 | 수신 탑(높이) |
| I 숫자 | 큐에 주어진 숫자 삽입 |
| D 1 | 큐에서 최댓값 삭제 |
| D -1 | 큐에서 최솟값 삭제 |
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해야 한다.
접근
최댓값을 저장할 우선순위큐 pQueue와 최솟값을 저장할 우선순위큐 rpQueue를 선언한다. 이후 각 명령어에 맞춰 연산을 진행하는데, I 숫자가 들어올 경우 pQueue와 rpQueue 모두에 해당 숫자를 저장한다. D 1이 들어올 경우 pQueue에서 poll한 값을 rpQueue에서 remove하고, D -1이 들어올 경우 rpQueue에서 poll한 값을 pQueue에서 remove한다.
마지막에 모든 연산을 처리한 후 큐가 비어있으면 [0,0]를 반환해야 하므로 pQueue와 rpQueue 모두 peek 값이 null값인지 확인해야 한다.
코드
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
PriorityQueue<Integer> pQueue = new PriorityQueue<>();
PriorityQueue<Integer> rpQueue = new PriorityQueue<>(Collections.reverseOrder());
for (String operation : operations) {
StringTokenizer st = new StringTokenizer(operation, " ");
char c = st.nextToken().charAt(0);
int i = Integer.parseInt(st.nextToken());
if (c == 'I') {
pQueue.offer(i);
rpQueue.offer(i);
} else if (c == 'D') {
if (!pQueue.isEmpty()) {
if (i == -1) {
rpQueue.remove(pQueue.poll());
} else {
pQueue.remove(rpQueue.poll());
}
}
}
}
return new int[] { rpQueue.peek() != null ? rpQueue.poll() : 0, pQueue.peek() != null ? pQueue.poll() : 0 };
}
}결론
생각보다 적을 말이 많았는데 문제가 3문제뿐이라 이번에도 역시 하나의 글에 모든 문제를 적어버렸다. 예전에 한창 알고리즘 공부를 열심히 할 때 풀었었던 문제들인데 2번은 안 풀어져있길래 당연히 이번에 새로 나온 문제인 줄 알았는데 그냥 틀린 문제였다. 내 코드를 보니 dfs로 접근하고 있었던데.. 과거의 나는 무슨 생각을 갖고 있던 걸까..?
그래도 운영체제 수업 때 과제로 작성했던 Project-CPU-Scheduler가 접근 과정에 도움이 됐던 것 같아서 나름 뿌듯한 감정이 들었다.