👀 문제
https://programmers.co.kr/learn/courses/30/lessons/42627
테스트케이스 추가
- 참고로 파라미터 jobs는 정렬이 되어있지않다. 이정도는 문제설명에 적어줘야 하는데. 떼잉쯧;
| jobs(int[][]) | return |
|---|---|
| [[24, 10], [18, 39], [34, 20], [37, 5], [47, 22], [20, 47], [15, 2], [15, 34], [35, 43], [26, 1]] | 74 |
| [[24, 10], [18, 39], [34, 20], [37, 5], [47, 22], [20, 47], [15, 34], [15, 2], [35, 43], [26, 1]] | 74 |
👊 첫 번째 도전
1. 설계
- 소요시간(time)이 작은 순서, 같다면 요청시간(start)이 작은 순서가 우선순위가 높도록 우선순위큐를 생성한다.
- 현재 시간(now)보다 요청시간이 같거나 작은 작업을 선택해 요청~종료까지 걸린 시간을 계산한 후 now와 answer을 갱신한다.
- 없으면 현재 시간엔 수행할 작업이 없다는 뜻이므로 now++한다.
- 계산이 끝나면 작업 갯수만큼 answer을 나눠 평균을 구한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.PriorityQueue;
import java.util.ArrayList;
/**
*
* @author HEESOO
*
*/
class Job implements Comparable<Job>{
int start;
int time;
public Job(int s, int t){
this.start=s;
this.time=t;
}
@Override
public int compareTo(Job j){
//소요시간 작은 게 우선순위 높음
if(this.time<j.time)return -1;
//소요시간이 같다면
else if(this.time==j.time){
if(this.start<j.start)return -1;//요청시점 작은게 우선순위 높음
else return 1;
}
else return 1;
}
}
class Solution {
public int solution(int[][] jobs) {
int answer = 0;
int now=0;
PriorityQueue<Job> pq=new PriorityQueue<Job>();
ArrayList<Job> list=new ArrayList<Job>();
for(int i=0;i<jobs.length;i++){
pq.offer(new Job(jobs[i][0],jobs[i][1]));
}
for(int i=0;i<pq.size();i++){
list.add(pq.poll());
}
Job job;
while(!list.isEmpty()){
for(int i=0;i<list.size();i++){
job=list.get(i);
if(job.start<=now){
answer+=now+job.time-job.start;
now+=job.time;
list.remove(job);
break;
}
if(i==list.size()-1){
now++;
}
}
}
answer/=jobs.length;
return answer;
}
}
3. 결과
실패.
출력문을 찍은 결과 list에 모든 값들이 들어가지 않았다.
4. 문제점
두 번째 for문에서 i의 범위가 pq.size()인데, pq는 팝하면서 제거되어 사이즈가 계속 변하므로 적합하지 않다.
👊 두 번째 도전
1. 설계
- pq.size()가 아닌 고정값 jobs.length로 for문 조건을 변경한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.PriorityQueue;
import java.util.ArrayList;
/**
*
* @author HEESOO
*
*/
class Job implements Comparable<Job>{
int start;
int time;
public Job(int s, int t){
this.start=s;
this.time=t;
}
@Override
public int compareTo(Job j){
//소요시간 작은 게 우선순위 높음
if(this.time<j.time)return -1;
//소요시간이 같다면
else if(this.time==j.time){
if(this.start<j.start)return -1;//요청시점 작은게 우선순위 높음
else return 1;
}
else return 1;
}
}
class Solution {
public int solution(int[][] jobs) {
int answer = 0;
int now=0;
PriorityQueue<Job> pq=new PriorityQueue<Job>();
ArrayList<Job> list=new ArrayList<Job>();
for(int i=0;i<jobs.length;i++){
pq.offer(new Job(jobs[i][0],jobs[i][1]));
}
for(int i=0;i<jobs.length;i++){
list.add(pq.poll());
}
Job job;
while(!list.isEmpty()){
for(int i=0;i<list.size();i++){
job=list.get(i);
if(job.start<=now){
answer+=now+job.time-job.start;
now+=job.time;
list.remove(job);
break;//작업이 완료되면 break로 다시 for문을 처음부터 방문하여 놓치는 작업이 없도록 한다
}
if(i==list.size()-1){
now++;
}
}
}
answer/=jobs.length;
return answer;
}
}
- PriorityQueue
pq: 소요시간이 작은 순서, 같다면 요청시간이 작은 순서로 정렬한다. - ArrayList
list: pq를 arraylist에 저장하여 코드에 사용한다. 같은 데이터를 가지고 있는데 굳이 arraylist에 저장하여 사용하는 이유는, pq가 요청시간을 기준으로 정렬된 것이 아니기 때문이다. 현재 시간(now)에 따라 이전~현재까지의 작업들을 모두 확인해야하는데, 우선순위큐로는 정렬된 루트노드의 값만 가져올 수 있고 다음 노드를 방문하기 위해서는 무조건 poll해야한다. 하지만 미래의 작업이 루트로 갈 수 있는데, 이때는 삭제하면 안되므로 arrayList를 이용해 값을 삭제하지 않아도 다음 값을 찾을 수 있게 한다.
3. 결과
🤟 성공 🤟
👏 해결 완료!
Compare을 Override하는 법에 대해 배울 수 있었다. 처음에는 jobs 배열을 요청시간 오름차순으로 정렬해서 사용하고 싶었는데, Array.sort()나 Collections.sort()를 사용하려고 하니 Override한 compare를 쓰는 바람에 애먹었다. 결국에는 배열을 정리할 필요 없이 처음부터 우선순위큐를 사용했는데, 이건 다른 사람 코드를 보고 나도 따라한 것이다. 나도 이렇게 바로 떠오르면 좋으련만.