๐ 1. ๋ฌธ์ ์ค๋ช
ํ๋๋์คํฌ๋ ํ ๋ฒ์ ํ๋์ ์์ ๋ง ์ํํ ์ ์์ต๋๋ค. ๋์คํฌ ์ปจํธ๋กค๋ฌ๋ฅผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์์ต๋๋ค. ๊ฐ์ฅ ์ผ๋ฐ์ ์ธ ๋ฐฉ๋ฒ์ ์์ฒญ์ด ๋ค์ด์จ ์์๋๋ก ์ฒ๋ฆฌํ๋ ๊ฒ์ ๋๋ค.
์๋ฅผ ๋ค์ด
- 0ms ์์ ์ 3ms๊ฐ ์์๋๋ A์์ ์์ฒญ
- 1ms ์์ ์ 9ms๊ฐ ์์๋๋ B์์ ์์ฒญ
- 2ms ์์ ์ 6ms๊ฐ ์์๋๋ C์์ ์์ฒญ
์ ๊ฐ์ ์์ฒญ์ด ๋ค์ด์์ต๋๋ค. ์ด๋ฅผ ๊ทธ๋ฆผ์ผ๋ก ํํํ๋ฉด ์๋์ ๊ฐ์ต๋๋ค.
ํ ๋ฒ์ ํ๋์ ์์ฒญ๋ง์ ์ํํ ์ ์๊ธฐ ๋๋ฌธ์ ๊ฐ๊ฐ์ ์์ ์ ์์ฒญ๋ฐ์ ์์๋๋ก ์ฒ๋ฆฌํ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ์ฒ๋ฆฌ ๋ฉ๋๋ค.
- A: 3ms ์์ ์ ์์ ์๋ฃ (์์ฒญ์์ ์ข ๋ฃ๊น์ง : 3ms)
- B: 1ms๋ถํฐ ๋๊ธฐํ๋ค๊ฐ, 3ms ์์ ์ ์์ ์ ์์ํด์ 12ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 11ms)
- C: 2ms๋ถํฐ ๋๊ธฐํ๋ค๊ฐ, 12ms ์์ ์ ์์ ์ ์์ํด์ 18ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 16ms)
์ด ๋ ๊ฐ ์์ ์ ์์ฒญ๋ถํฐ ์ข ๋ฃ๊น์ง ๊ฑธ๋ฆฐ ์๊ฐ์ ํ๊ท ์ 10ms(= (3 + 11 + 16) / 3)๊ฐ ๋ฉ๋๋ค.
ํ์ง๋ง A → C → B ์์๋๋ก ์ฒ๋ฆฌํ๋ฉด
- A: 3ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 3ms)
- C: 2ms๋ถํฐ ๋๊ธฐํ๋ค๊ฐ, 3ms ์์ ์ ์์ ์ ์์ํด์ 9ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 7ms)
- B: 1ms๋ถํฐ ๋๊ธฐํ๋ค๊ฐ, 9ms ์์ ์ ์์ ์ ์์ํด์ 18ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 17ms)
์ด๋ ๊ฒ A → C → B์ ์์๋ก ์ฒ๋ฆฌํ๋ฉด ๊ฐ ์์ ์ ์์ฒญ๋ถํฐ ์ข ๋ฃ๊น์ง ๊ฑธ๋ฆฐ ์๊ฐ์ ํ๊ท ์ 9ms(= (3 + 7 + 17) / 3)๊ฐ ๋ฉ๋๋ค.
๊ฐ ์์ ์ ๋ํด [์์ ์ด ์์ฒญ๋๋ ์์ , ์์ ์ ์์์๊ฐ]์ ๋ด์ 2์ฐจ์ ๋ฐฐ์ด jobs๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์์ ์ ์์ฒญ๋ถํฐ ์ข ๋ฃ๊น์ง ๊ฑธ๋ฆฐ ์๊ฐ์ ํ๊ท ์ ๊ฐ์ฅ ์ค์ด๋ ๋ฐฉ๋ฒ์ผ๋ก ์ฒ๋ฆฌํ๋ฉด ํ๊ท ์ด ์ผ๋ง๊ฐ ๋๋์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. (๋จ, ์์์ ์ดํ์ ์๋ ๋ฒ๋ฆฝ๋๋ค)
์ ํ ์ฌํญ
- jobs์ ๊ธธ์ด๋ 1 ์ด์ 500 ์ดํ์ ๋๋ค.
- jobs์ ๊ฐ ํ์ ํ๋์ ์์ ์ ๋ํ [์์ ์ด ์์ฒญ๋๋ ์์ , ์์ ์ ์์์๊ฐ] ์ ๋๋ค.
- ๊ฐ ์์ ์ ๋ํด ์์ ์ด ์์ฒญ๋๋ ์๊ฐ์ 0 ์ด์ 1,000 ์ดํ์ ๋๋ค.
- ๊ฐ ์์ ์ ๋ํด ์์ ์ ์์์๊ฐ์ 1 ์ด์ 1,000 ์ดํ์ ๋๋ค.
- ํ๋๋์คํฌ๊ฐ ์์ ์ ์ํํ๊ณ ์์ง ์์ ๋์๋ ๋จผ์ ์์ฒญ์ด ๋ค์ด์จ ์์ ๋ถํฐ ์ฒ๋ฆฌํฉ๋๋ค.
์ ์ถ๋ ฅ ์
jobs | return |
[[0,3], [1,9], [2,6]] | 9 |
์ ์ถ๋ ฅ ์ ์ค๋ช
- 0ms ์์ ์ 3ms ๊ฑธ๋ฆฌ๋ ์์ ์์ฒญ์ด ๋ค์ด์ต๋๋ค.
- 1ms ์์ ์ 9ms ๊ฑธ๋ฆฌ๋ ์์ ์์ฒญ์ด ๋ค์ด์ต๋๋ค.
- 2ms ์์ ์ 6ms ๊ฑธ๋ฆฌ๋ ์์ ์์ฒญ์ด ๋ค์ด์ต๋๋ค.
๐ก 2. ์ ๊ทผ๋ฐฉ์
์ผ๋จ ์ด ๋ฌธ์ ๋ฅผ ๋ณด๊ณ ํ๋ก์ธ์ค ์ค์ผ์ค๋ง์ด ์๊ฐ๋ฌ๋ค. SJF(Shortest Job First)๋ผ๋ ์ค์ผ์ค๋ง ๊ธฐ๋ฒ์ ๋ ์ฌ๋ฆฌ๊ฒ ํ๋ ๋ฌธ์ ์ด๋ค. ์ํ ์๊ฐ์ด ๊ฐ์ฅ ์งง์ ๊ฒ๋ถํฐ ์ํํ๋๋ฐ, ๋น์ ์ ํ์ด๊ธฐ ๋๋ฌธ์ ์ค๊ฐ์ ๋ค๋ฅธ ํ๋ก์ธ์ค๊ฐ ์์ ์ ๊ฐ์ ๋ก ๋นผ์์ ์ฌ ์๋ ์๋ค.
์ฉ์ด ์ค๋ช
์์ ์์ฒญ๋ถํฐ ์๋ฃํ๋๋ฐ ๊ฑธ๋ฆฐ ์๊ฐ์ ์์ผ๋ก ํด์ด๋ผ์ด๋ํ์์ด๋ผ๊ณ ๋ถ๋ฅด๊ฒ ์.
ํด์ด๋ผ์ด๋ ํ์์ ํ๋ก์ธ์ค๊ฐ ์์คํ ์ ์์ฒญ๋ ์์ ๋ถํฐ ์คํ๋์ด ์๋ฃ๋ ๋๊น์ง ๊ฑธ๋ฆฐ ์ ์ฒด ์๊ฐ์ ๋ปํ๋ค.
ํด์ด๋ผ์ด๋ ํ์(Turnaround Time)**์ ์๋ฃ ์๊ฐ - ์์ฒญ ์๊ฐ์ผ๋ก ๋๋ค.
๊ทธ๋ฆฌ๊ณ ํด์ด๋ผ์ด๋ ํ์์ **๋๊ธฐ ์๊ฐ(Waiting Time) + ์คํ ์๊ฐ(Burst Time)**์ ํฉ๊ณผ ๋์ผํํ๋ค.
์ด ๋ฌธ์ ์์ ์ฃผ์ด์ง ์กฐ๊ฑด์ผ๋ก๋ ์๋ ๊ณต์์ ํ์ฉํ ์ ์๋ค.
ํด์ด๋ผ์ด๋ํ์ = ์๋ฃ์๊ฐ - ์์ฒญ์๊ฐ
๋ฌธ์ ์์ ์ ์ ์๋ ๊ฒ
- ํ์ฌ์์ ์ ์์ฒญ์๊ฐ `temp[0]`
- ํ์ฌ์์ ์ ์์์๊ฐ `temp[1]`
- ํ์ฌ ์๊ฐ(์์ ์ด ์์๋๊ธฐ ์ ์์ ) `sec`
์๋ฃ์๊ฐ ๊ณ์ฐ
์์ ์ด ์์๋๊ธฐ ์ ์์ ์ ์์์๊ฐ์ ๋ํ ๊ฐ
์๋ฃ ์๊ฐ= `sec` +`temp[1]`
ํด์ด๋ผ์ด๋ํ์ = ์๋ฃ์๊ฐ - ์์ฒญ์๊ฐ
ํด์ด๋ผ์ด๋ ํ์ = (sec+temp[1]) − temp[0]
ํด์ด๋ผ์ด๋ ํ์= sec − temp[0] + temp[1]
PriorityQueue (์ฐ์ ์์ํ)
๋จผ์ ๋์ฐฉ ์๊ฐ์ด ๋น ๋ฅธ ๊ฒ(jobs[0])๋ถํฐ ์ค๋ฆ์ฐจ์์ผ๋ก ๋ฐฐ์ด์ ์ ๋ ฌ ํด ์ค๋ค.
ํ์ฌ ์๊ฐ๋ณด๋ค ์ด์ ์ ์์ฒญ์ด ๋ค์ด์จ ์์ ์ ํ์ ์ถ๊ฐํด ์ค๋ค.
์ด ๋ ์ฐ์ ์์ ํ๋ ์์์๊ฐ์ด ์ ์ ๊ฒ(jobs[1])๋ถํฐ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ ํ๋ค.
ํ์ ๊ฐ ์์ ์ ์์ฒญ๋ถํฐ ์ข ๋ฃ๊น์ง ๊ฑธ๋ฆฐ ์๊ฐ์ sum์ ๋์ ํด์ ๋ด์ ์ฃผ๊ณ ๋ง์ง๋ง์ jobs.length()๋ก ๋๋์ด ์ฃผ๋ฉด ์ด ํด์ด๋ผ์ด๋ ํ์์ ํฉ์ ํ๊ท ์ ๋ฆฌํดํ๋ค.
๋ง์ฝ ํ์ฌ ์๊ฐ ์ด์ ์ ๋ค์ด์จ ์์ ์ด ์๋ค๋ฉด?
๋ค์ ์์ ์ด ์์ฒญ๋๋ ์์ ์ผ๋ก ํ์ฌ ์๊ฐ์ ์ด๋ ํด ์ค๋ค.
์ฆ, ๋ค์ ์์ ์ ์์ฒญ์๊ฐ์ผ๋ก sec ๊ฐ์ ๋ฐ๊ฟ์ค๋ค.
โญ 3. ์ฝ๋
import java.util.PriorityQueue;
import java.util.Arrays;
class Solution {
public int solution(int[][] jobs) {
int sum = 0;
// ์์ฒญ์๊ฐ์ผ๋ก ๋ฐฐ์ด ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
Arrays.sort(jobs, (o1, o2) -> (o1[0] - o2[0]));
// ์์์๊ฐ์ผ๋ก ํ ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> (o1[1] - o2[1]));
// ํ์ฌ์๊ฐ
int sec = 0;
// ํ์ฌ ์์
์ธ๋ฑ์ค
int idx = 0;
// ๋ช ๊ฐ์ ์์
์ด ์ฒ๋ฆฌ๋์๋์ง
int cnt = 0;
// ์ฒ๋ฆฌ๋ ์์
์ด jobs.length ๋ณด๋ค ์์ ๋๊น์ง ๋ฐ๋ณต
while(cnt < jobs.length) {
// ํ์ฌ ์ธ๋ฑ์ค๊ฐ job.length ๋ณด๋ค ์๊ณ and
// ํ์ฌ sec์ผ ๋ ํ์ ๋ค์ด๊ฐ ์ ์๋(sec๋ณด๋ค ์์ฒญ์์ ์ด ๊ฐ๊ฑฐ๋ ์์)
// ์์๋ค์ ํ์ ์ถ๊ฐ
while(idx < jobs.length && jobs[idx][0] <= sec) {
q.add(jobs[idx++]);
}
// ํ๊ฐ ๋น์ด ์์ผ๋ฉด ๋ค์ ์์
์ ์์ฒญ ์๊ฐ์ผ๋ก ํ์ฌ ์๊ฐ์ ์ด๋
if(q.isEmpty()) {
//
sec = jobs[idx][0];
// ํ์ ์์
์ด ๋ค์ด์ ์์ผ๋ฉด
// ๊ฐ์ฅ ์์ ์๊ฐ์ด ์งง์ ์์
์ ๊บผ๋ด ์ฒ๋ฆฌ
} else {
// ํ์์ ๋บ ์์
๋ด์์ค int[]ํ temp ๋ณ์
int[] temp = q.poll();
// ์ด ์ฒ๋ฆฌ์๊ฐ = ์์์๊ฐ + ๋๊ธฐ์๊ฐ
// ์ด ์ฒ๋ฆฌ์๊ฐ = ์์์๊ฐ + (ํ์ฌ์๊ฐ - ์์
์์ฒญ์๊ฐ)
sum += temp[1] + (sec - temp[0]);
// ํ์ฌ ์๊ฐ์ ์์
์ด ์ฒ๋ฆฌ๋ ์๊ฐ๋งํผ ์ฆ๊ฐ
sec += temp[1];
// ์ฒ๋ฆฌ๋ ์์
์ฆ๊ฐ
cnt++;
}
}
return sum/jobs.length;
}
}
๐๐ป 4. ๊ฐ์ ์ ํ ๋ฌธ์ (์ฐ์ ์์ํ)