๐ ํ๋ก๊ทธ๋๋จธ์ค ๋์คํฌ ์ปจํธ๋กค๋ฌ CPP
๐ ์ฒซ ๋ฒ์งธ ํ์ด
- ์ฝ๋ ์๋ : ๋ถ๋ฅ๋ ํ์ธ๋ฐ.. ๋ญ์ง ๋ชจ๋ฅด๊ฒ ๋ค.,
- ๊ฒฐ๊ณผ : ์ ํ์ฑ 100์ (20/20), ์ด 100์
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(vector<int> v1, vector<int> v2)
{
if (v1[1] == v2[1])
return v1[0] < v2[0];
return v1[1] < v2[1];
}
int solution(vector<vector<int>> jobs)
{
sort(jobs.begin(), jobs.end(), compare);
bool* completed = new bool[jobs.size()];
for (int i = 0; i < jobs.size(); i++)
completed[i] = false;
int lastCompletedTime = 0;
int sumOfElapsedTime = 0;
for (int i = 0; i < jobs.size(); i++)
{
int curProcessIndex = -1;
int earliestReqTime = 1001;
int earliestReqIndex = -1;
// ๋ค์ ์์
์ ์ฐพ๋๋ค.
// ๋ง์ฝ ๋น์ฅ ์์ํ ์ ์๋ ์์
์ด ์๋ ๊ฒฝ์ฐ, ๋จ์ ์์
์ค ๊ฐ์ฅ ๋จผ์ ์์ฒญ๋ ์์
์ ์ฐพ๋๋ค.
for (int ji = 0; ji < jobs.size(); ji++)
{
if (completed[ji])
continue;
if (jobs[ji][0] < earliestReqTime)
{
earliestReqTime = jobs[ji][0];
earliestReqIndex = ji;
}
if (jobs[ji][0] > lastCompletedTime)
continue;
completed[ji] = true;
curProcessIndex = ji;
break;
}
if (curProcessIndex != -1)
{
sumOfElapsedTime += jobs[curProcessIndex][1] + (lastCompletedTime - jobs[curProcessIndex][0]);
lastCompletedTime += jobs[curProcessIndex][1];
}
else
{
int breakTime = earliestReqTime - lastCompletedTime;
completed[earliestReqIndex] = true;
sumOfElapsedTime += jobs[earliestReqIndex][1] + earliestReqTime - jobs[earliestReqIndex][0];
lastCompletedTime += jobs[earliestReqIndex][1] + breakTime;
}
}
delete[] completed;
return sumOfElapsedTime / jobs.size();
}
์๋ฃ๊ตฌ์กฐ์์ ํ์ ๋ฐฐ์ฐ๊ธด ํ์์ง๋ง..
์ด๋ป๊ฒ ์ธ์ง๋ฅผ ๋ชฐ๋ผ ๊ทธ๋ฅ ๋ฌด์์ ํ์๋ค.
์ญ์ ๋ ์ค์ค๋ก๊ฐ ๋ง์ด ๋ถ์กฑํ๋ค๊ณ ๋๊ผ๋ค.
๐ ์ต์ข ํ์ด
- ์ฝ๋ ์๋ : ์ข์๋ณด์ด๋ ํ์ด๋ฅผ ๋ณด๊ณ ๋ฐฐ๋ผ์, (Priority Queue, Template, Iterator)
- ๊ฒฐ๊ณผ : ์ ํ์ฑ 100์ (20/20), ์ด 100์
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
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct CompareProcessTime
{
bool operator()(const vector<int>& v1, const vector<int>& v2)
{
// ์ฐ์ ์์ ํ๋ ํฐ ๊ฒ ์์๋๋ก ์ ๋ ฌํ๊ธฐ ๋๋ฌธ์,
// ์ค๋ฆ์ฐจ์์ผ๋ก ๋ง๋ค์ด์ฃผ๊ธฐ ์ํด์๋ ์ ๋ ฌ ์์๋ฅผ ๋ฐ๋๋ก
return v1[1] > v2[1];
}
};
struct CompareReqTime
{
bool operator()(const vector<int>& v1, const vector<int>& v2)
{
return v1[0] < v2[0];
}
};
int solution(vector<vector<int>> jobs)
{
priority_queue<vector<int>, vector<vector<int>>, CompareProcessTime> pq;
sort(jobs.begin(), jobs.end(), CompareReqTime());
auto it = jobs.begin();
int sumOfElapsedTime = 0;
int curTime = jobs[0][0];
while ((it != jobs.end()) || !pq.empty())
{
while ((it != jobs.end()) && ((*it)[0] <= curTime))
{
pq.push((*it));
it++;
}
if (!pq.empty())
{
curTime += pq.top()[1];
sumOfElapsedTime += (curTime - pq.top()[0]);
pq.pop();
}
else
{
curTime = (*it)[0];
}
}
return sumOfElapsedTime / jobs.size();
}
๋ค๋ฅธ ๋ถ๋ค์ ํ์ด๋ฅผ ๋ณด๋ค๊ฐ, ์ ์ผ ๊น๋ํด๋ณด์ด๋ ์ฝ๋๊ฐ ์ด๊ฑฐ์๋ค.
CPP์ Priority Queue, Template, Iterator๋ฅผ ์ด๋ฒ์ ๋ฐฐ์ ๋ค.
Priority Queue๋ ๊ธฐ๋ณธ์ ์ผ๋ก ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌ์ ํ๊ธฐ์,
์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋๋ Compare ๊ตฌ์กฐ์ฒด๋ฅผ ๋ง๋ค ๋ ๋ฆฌํด์ ๋ฐ๋๋ก ์ค์ผํ๋ค.
์ฐ์ ์์๊ฐ ๋ ๋์ ๊ฒ์ true๋ฅผ ๋ฆฌํดํด์ค์ผ ํ๋ค.
Compare ๊ตฌ์กฐ์ฒด๋ ์ฌ์ค ์ด๋ฒ์ ์์๋ค.
๊ธฐ์กด์๋ ์ฒซ ๋ฒ์งธ ํ์ด์ฒ๋ผ Compare ํจ์๋ฅผ ๋ง๋ค์ด ๋ฃ์์๋๋ฐ,
๊ดํธ ์ฐ์ฐ์๋ฅผ ์ฌ์ ์ํ๋ ๊ตฌ์กฐ์ฒด๋ ์ด๋ฒ์ ์ฒ์ ์จ๋ณด์๋ค.
Template์ ๋ชจ๋์ ์ฝ๋์์ ๊ณต๋ถํ๋ค.
๊ถ๊ธํ ๊ฒ๋ค์ด ์ฃ๋ค ์์ด์ ์ ์ตํ๋ค.
Iterator๋ C#๋ ๋น์ทํ ๊ฒ ๊ฐ์๋ฐ,
์ฌ์ค C#์์๋ ๋ณ๋ก ์จ๋ณธ์ ์ด ์์ด์.. ใ
ใ
..
๋ ๊ณต๋ถํด๋ด์ผ ํ ๊ฒ ๊ฐ๋ค.
Container Adapter? ๋ผ๋ ๊ฒ๋ ์ ์๋ฟ์ง์๋๋ค.
๋ง์ฐฌ๊ฐ์ง๋ก ๋ ๊ณต๋ถํด์ผ๊ฒ ๋ค..