티스토리 뷰
코딩테스트 연습 - 디스크 컨트롤러
하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를��
programmers.co.kr
이문제는 작업 수행 시 어떤 순서로 진행을 해야 하는가를 계산하는 문제이다. 작업할 수 있는 시간에 요청이 들어와 있는 작업 중 수행 시간이 짧은 작업을 선택하여 먼저 실행하면 되는 문제였다. 처음에는 간단하다고 생각했는데 문제를 잘 읽어봐야 한다 역시... 요청 시간 순으로 jobs배열이 구성된다는 내용은 어디에도 없었다 ㅎ,,
문제풀이
-모든 작업을 수행할 때까지 cnt 카운트를 진행한다.
-time은 계속 흘러가고 time==jobs [i][0](요청 시간) 일 경우 우선순위 큐에 저장한다.
-큐에는 요청 시 간과 수행 시간이 쌍으로 담긴 Task 클래스를 만들어 저장한다.
-우선순위 큐의 정렬 방식: 작업을 처리할 수 있는 것만 들어왔으므로(time==jobs [i][0](요청 시간) 이 과정을 통해) 수행 시간이 적은 것을 우선으로 정렬한다. 만약 같을 경우 요청이 먼저 들어온 것을 우선으로 정렬한다.
※ 내가 헤맸던 부분은 jobs배열이 요청 순서대로 정렬되어있지 않다는 점과, 같은 시간에 여러 개의 요청이 들어올 수 있다는 점! 나는 이 부분을 while 문을 돌 때마다 해당하는 jobs배열 요소 모두를 큐에 넣을 수 있게 for문을 사용했다. 시간 초과가 날까 했지만 통과!
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class DiskController {
public static void main(String[] args) {
int[][] jobs = { { 0, 9 }, { 0, 4 }, { 0, 5 },{0,7} ,{0,3}};//testcase 답:13
int time = 0;
int answer = 0;
int finishT = 0;
int cnt = 0;
PriorityQueue<Task> minHeap = new PriorityQueue<>();
//모든 작업이 수행될 수 있도록 cnt
while (cnt < jobs.length) {
//해당타임에 요청한 작업 모두 큐에 저장
for(int i=0;i<jobs.length;i++){
if (time == jobs[i][0]) {
minHeap.add(new Task(jobs[i][0], jobs[i][1]));
}
}
//time이 작업이 끝난 이후고 큐에 작업요청이 있다면
//answer,작업이끝날시간(finishT) 갱신
if ((time >= finishT) && !minHeap.isEmpty()) {
Task task = minHeap.poll();
answer += time - task.start + task.executeT;
finishT = time + task.executeT;
cnt++;
}
time++;
}
System.out.println(answer / jobs.length);
}
}
//정렬기준 정해주기
class Task implements Comparable<Task> {
int start;
int executeT;
Task(int start, int executeT) {
this.start = start;
this.executeT = executeT;
}
//수행시간 오름차순으로, 같을경우 요청시간 오름차순으로
@Override
public int compareTo(Task t) {
if (this.executeT < t.executeT)
return -1; // 오름차순
else if (this.executeT == t.executeT) {
if (this.start < t.start)
return -1;
}
return 1;
}
}
'CS공부 > 알고리즘&문제풀이' 카테고리의 다른 글
[프로그래머스]완전탐색:소수 찾기(java) (0) | 2020.07.08 |
---|---|
[프로그래머스]힙(Heap):이중우선순위큐(java) (0) | 2020.07.05 |
[프로그래머스]힙(Heap):라면공장(java) (0) | 2020.06.28 |
[백준 17140]이차원 배열과 연산/삼성 sw역량 테스트 기출(java) (0) | 2020.06.21 |
[프로그래머스]해시:전화번호 목록(java) (0) | 2020.06.18 |
- Total
- Today
- Yesterday
- OS
- DP
- BFS
- Oracle
- git
- dfs
- Spring
- 자바
- 운영체제
- 알고리즘
- SWEA
- 최소 스패닝 트리
- 백준
- JavaScript
- Baekjoon
- 분리 집합
- programers
- 완전탐색
- websocket
- MST
- 채팅
- Heap
- 삼성 sw역량테스트
- 정렬
- sockjs
- java
- 코딩테스트
- 프로그래머스
- 삼성 sw역량 테스트
- Stomp
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |