이 파트에 되게 취약하다.....
전에 전공 복습에서 힙을 공부 했었다. 이번에는 c++로 객체 지향으로 구현해 보자.
문제는 최소 힙을 구현하면 된다. 그리고 최소힙 팝, 푸쉬를 구현하면 된다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
- scoville의 길이는 1 이상 1,000,000 이하입니다.
- K는 0 이상 1,000,000,000 이하입니다.
- scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
- 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
길이가 100만이다.
음 힙을 구현하느라 애를 많이 먹었다. 버블 다운 방식, 바텀 업 방식.
#include <string>
#include <vector>
#include<iostream>
using namespace std;
using ll = long long int;
class Heap {
private:
ll heap[2000001] = { 0 };
int size = 0;
public:
void push(ll x);
ll pop();
ll front();
int get_size();
};
int Heap::get_size() {
return size;
}
ll Heap::front() {
return heap[1];
}
ll Heap::pop() {
ll ans = heap[1];
int parent = 1;
int child = 2;
int greater;
if (size == 0)
return -1;
heap[parent] = heap[size--];
while (size >= child) {
greater = heap[child] > heap[child + 1] ? child + 1 : child;
if (heap[parent] > heap[greater]) {
ll tmp;
tmp = heap[parent];
heap[parent] = heap[greater];
heap[greater] = tmp;
}
parent = greater;
child = greater * 2;
}
return ans;
}
void Heap::push(ll x) {
int i = (++size);
while (1) {
if (heap[i / 2] > x) {
ll tmp = heap[i];
heap[i] = heap[i / 2];
heap[i / 2] = tmp;
i = i / 2;
}
else
{
break;
}
}
heap[i] = x;
}
Heap hp;
int solution(vector<int> scoville, int K) {
int answer = 0;
for (int i = 0; i < scoville.size(); i++) {
hp.push(scoville[i]);
}
int cnt = 0;
while (hp.front() <= K) {
if (hp.get_size() == 1) {
answer = -1;
return answer;
}
ll newScov = hp.pop() + hp.pop() * 2;
hp.push(newScov);
cnt++;
}
answer = cnt;
return answer;
}
라면 공장
현재 날짜와 stock을 기준으로 잘 해보면 될거 같다.
1일에는 stock이 4
2일 3
3일 2
4일 1 -> 1이므로 내일 없으니까 dates를 보고 현재 날짜보다 작거나 같은 놈들은 supply 해주면 합리적인거 같다.
5일 0
그런데 date가 오름 차순으로 주어지므로 그냥 queue에 넣으면 될거 같다.
queue에서 pop_front를 사용하려고 list를 구현해서 했는데 틀렸다......
#include <string>
#include <vector>
#include<iostream>
using namespace std;
typedef struct elem {
int val;
elem * next;
};
class LinkedList {
private:
elem * head= NULL;
public:
void push(int x);
void pop_front();
int front();
};
void LinkedList::push(int x) {
if (head == NULL) {
elem* node = new elem();
node->val = x;
head = node;
}
else {
elem * cur= head;
while (cur->next != NULL) {
cur = cur->next;
}
elem* node = new elem();
node->val = x;
cur->next = node;
}
}
void LinkedList::pop_front() {
elem * cur = head;
head = head->next;
delete cur;
return;
}
int LinkedList::front() {
if (head == NULL)
return -1;
return head->val;
}
LinkedList list;
int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
int answer = 0;
int cnt = 0;
for (int i = 0; i < dates.size(); i++) {
list.push(dates[i]);
}
for (int i = 1; i < k; i++) {
if (stock ==1) {
while (list.front() != -1 && list.front() <= i) {
stock += supplies[cnt];
list.pop_front();
cnt++;
}
answer++;
}
stock--;
}
cout << answer;
return answer;
}
void main() {
vector<int> tmp;
vector<int> tmp2;
tmp.push_back(4);
tmp.push_back(10);
tmp.push_back(15);
tmp2.push_back(20);
tmp2.push_back(5);
tmp2.push_back(10);
solution(4,tmp,tmp2,30);
}
아 문제를 잘못 이해했다.
stock dates supplies k result
| 4 | [4,10,15] | [20,5,10] | 30 | 2 |
입출력 예 설명
- 현재 밀가루가 4톤 남아 있기 때문에 오늘과 1일 후~3일 후까지 사용하고 나면 모든 밀가루를 다 사용합니다. 따라서 4일 후에는 반드시 밀가루를 공급받아야 합니다.
- 4일째 공급받고 나면 15일 이후 아침에는 9톤의 밀가루가 남아있게 되고, 이때 10톤을 더 공급받으면 19톤이 남아있게 됩니다. 15일 이후부터 29일 이후까지 필요한 밀가루는 15톤이므로 더 이상의 공급은 필요 없습니다.
- 따라서 총 2회의 밀가루를 공급받으면 됩니다.
나는 date가 지나도 공급 받을 수 있다고 생각했는데 그냥 그 날에만 공급받을 수 있는거다. 누적해서 공급을 한꺼번에 받지 못한다.
그러면 날짜를 경과시키며 stock을 소모하다가 공급 받을 수 있는 날이 되면 그 다음 공급일까지 stock이 충분한지 확인하고 충분하지 못하면 현재 supply를 공급받자.
바꿔도 자꾸 틀리는데 왜 틀린지 모르겠다....
#include <string>
#include <vector>
#include<iostream>
using namespace std;
typedef struct elem {
int val;
elem * next;
};
class LinkedList {
private:
elem * head = NULL;
int Size = 0;
public:
void push(int x);
void pop_front();
int front();
int front2();
bool isEmpty();
};
bool LinkedList::isEmpty() {
if (Size == 0)return true;
else return false;
}
void LinkedList::push(int x) {
if (head == NULL) {
elem* node = new elem();
node->val = x;
head = node;
}
else {
elem * cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
elem* node = new elem();
node->val = x;
cur->next = node;
}
Size++;
}
void LinkedList::pop_front() {
elem * cur = head;
head = head->next;
delete cur;
Size--;
return;
}
int LinkedList::front() {
if (head == NULL)
return -1;
return head->val;
}
int LinkedList::front2() {
if (head == NULL || head->next == NULL)
return -1;
return head->next->val;
}
LinkedList Dates;
LinkedList Supplies;
int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
int answer = 0;
int cnt = 0;
for (int i = 0; i < dates.size(); i++) {
Dates.push(dates[i]);
Supplies.push(supplies[i]);
}
int stock_left = stock;
int due;
while (!Dates.isEmpty()) {
if (Dates.front2() == -1)
due = k;
else
due = Dates.front2();
if (due < stock_left) {
Dates.pop_front();
Supplies.pop_front();
}
else {
stock_left += Supplies.front();
Dates.pop_front();
Supplies.pop_front();
answer++;
}
}
cout << answer;
return answer;
}
음 생각해보니까 알거 같기도 하다. 링크드 리스트라서 삽엡에 시간이 오래걸려서 아무래도 시간초과가 발생하는건가?
head에다 더해서 end를 추가하니까 시간 초과 문제는 해결한거 같다. 그래도 7점 맞음.
도저히 모르겠어서 일단 디스크 컨트롤러를 하자.
다른 분한테 물어보니까. 이것을 공급량이 큰 것부터 확인하는게 문제 목적에 맞다고 생각한다 했다. 듣고 보니 그게 맞는거 같다. 나는 왜 날짜 순으로 하려했을까 문제를 풀다가 해결해야되는 것을 잃어버리는 거 같다. 결국 K보다 커지게 하는 공급을 최소한으로 하면 되는데 그것을 몇번하면 되나의 문제가 아닌가?
단 내가 걱정되었된 서플라이가 당장은 공급 안된다 해서 팝했다가 다시 사용 못하면 안되서 걱정한건데, 그냥 팝해놓고 다시 푸쉬하면 될거같은데?
힙에서 child, parent , Size를 잘못 조절했었어서 틀렸었었다. 즉 힙 구현이 틀렸었다.
그리고 조건을 잘못 했다.
while (nStock < k) {
위에를 등호로 했었다. 등호면 할 필요 없는거 ㅠ , 이런 조건이 너무 햇갈린다.
그리고 stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다. 이런말도 어떻게 적용해야 될지 햇갈리고 .....
#include <string>
#include <vector>
#include<iostream>
using namespace std;
typedef struct elem {
int val;
elem * next;
};
class LinkedList {
private:
elem * head = NULL;
elem * end = NULL;
int Size = 0;
public:
void push(int x);
void pop_front();
int front();
int front2();
bool isEmpty();
};
bool LinkedList::isEmpty() {
if (Size == 0)return true;
else return false;
}
void LinkedList::push(int x) {
if (end == NULL) {
elem* node = new elem();
node->val = x;
head = node;
end = head;
}
else {
elem* node = new elem();
node->val = x;
end->next = node;
end = node;
}
Size++;
}
void LinkedList::pop_front() {
elem * cur = head;
head = head->next;
delete cur;
Size--;
return;
}
int LinkedList::front() {
if (head == NULL)
return -1;
return head->val;
}
int LinkedList::front2() {
if (head == NULL || head->next == NULL)
return -1;
return head->next->val;
}
LinkedList Dates;
LinkedList Supplies;
int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
int answer = 0;
int cnt = 0;
for (int i = 0; i < dates.size(); i++) {
Dates.push(dates[i]);
Supplies.push(supplies[i]);
}
int stock_left = stock;
int due;
while (!Dates.isEmpty()) {
if (Dates.front2() == -1)
due = k;
else
due = Dates.front2();
if (due <= stock_left) {
Dates.pop_front();
Supplies.pop_front();
}
else {
stock_left += Supplies.front();
Dates.pop_front();
Supplies.pop_front();
answer++;
}
}
cout << answer;
return answer;
}
다른 사람 코드는 이해가 안된다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
int answer = 0;
priority_queue<int> pq;
int start = 0;
while (stock < k)
{
for (int i = start; i < dates.size(); i++) {
if (dates[i] <= stock) {
pq.push(supplies[i]);
}
else {
start = i;
break;
}
}
answer++;
stock += pq.top();
pq.pop();
}
return answer;
}
디스크 컨트롤러
문제를 보니 그냥 가장 빨리 끝나는 놈부터 끝내면 될거 같은 기분이 든다......
그리고 시작일과 걸리는 시간 적절히 더해서 답을 구하면 될거 같다.
음 틀렸다. 그런데 도대체 왜~.. 20점 맞음
#include <string>
#include <vector>
#include <iostream>
#define N 500
using namespace std;
//최소 힙.
class Heap {
private:
int Size=0;
int arr[N * 2 + 1] = { 0 };
public:
void push(int x);
int front();
void pop_front();
void swap(int *a, int *b);
};
void Heap::swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void Heap::push(int x) {
int parent;
Size++;
arr[Size] = x;
parent = Size / 2;
if (Size >= 2) {
while (parent != 0 && arr[parent] > arr[Size]) {
swap(&arr[parent], &arr[Size]);
parent = parent / 2;
}
}
}
int Heap::front() {
if (Size >= 0)
return arr[1];
else
return -1;
}
void Heap::pop_front() {
int parent = 1;
int left, right;
swap(&arr[parent], &arr[Size]);
left = parent * 2;
right = parent * 2 + 1;
while (right < Size) {
int smaller = arr[left] < arr[right] ? left : right;
if (arr[parent] > arr[smaller]) {
swap(&arr[parent], &arr[smaller]);
}
else {
break;
}
parent = smaller;
left = parent * 2;
right = parent * 2 + 1;
}
Size--;
}
Heap endTime;
Heap startTime;
int solution(vector<vector<int>> jobs) {
int answer = 0;
for (int i = 0; i < jobs.size(); i++) {
endTime.push(jobs[i][1]);
startTime.push(jobs[i][0]);
}
int now = endTime.front() + startTime.front();
int stacked = endTime.front() - startTime.front();
endTime.pop_front();
startTime.pop_front();
//cout << stacked << "\n";
int tmp;
for (int i = 1; i < jobs.size(); i++) {
if (startTime.front() < now) {
tmp = (now - startTime.front() + endTime.front());
stacked += tmp;
}
else {
tmp = endTime.front();
stacked += tmp;
}
//cout << stacked << "\n";
//cout << tmp << "\n";
now += endTime.front();
startTime.pop_front();
endTime.pop_front();
}
answer = stacked/jobs.size();
return answer;
}
라면 공장 풀고 다시 보니까. 이것도 뭘 먼저 처리해야 되는 가에서 먼저 끝나는게 아니라, 현재 실행 할 수 있는 것중에 가장 짧은 것을 먼저 실행해야 빨리 끝난다.
그런데 어떤 놈으로 시작을 하지. 0초에는 시작할 수 있는게 없을 수 도 있지 않나? 최소 시작일은 알고 시작해야 될듯.
음 틀렸다. 생각해 보니. A를 종료하고 조금 텀이 있다가 B를 할 수 도 있잔아. 그러면 pq가 비어있어서 내 코드는 에러가 발생할 것이다.
#include <string>
#include <vector>
#include <iostream>
#include<algorithm>
#define N 500
using namespace std;
struct elem {
int st=-1, elapsed=-1;
};
//최소 힙.
class Heap {
private:
int Size = 0;
elem arr[N * 2 + 1];
public:
void push(elem x);
elem front();
void pop_front();
void swap(elem *a, elem *b);
bool empty();
};
bool Heap::empty() {
if (Size == 0) {
return true;
}
else {
return false;
}
}
void Heap::swap(elem *a, elem*b) {
elem tmp = *a;
*a = *b;
*b = tmp;
}
void Heap::push(elem x) {
int parent;
Size++;
arr[Size] = x;
parent = Size / 2;
if (Size >= 2) {
while (parent != 0 && arr[parent].elapsed > arr[Size].elapsed) {
swap(&arr[parent], &arr[Size]);
parent = parent / 2;
}
}
}
elem Heap::front() {
elem empty;
if (Size >= 0)
return arr[1];
else
return empty;
}
void Heap::pop_front() {
int parent = 1;
int left, right;
swap(&arr[parent], &arr[Size]);
left = parent * 2;
right = parent * 2 + 1;
while (right < Size) {
int smaller = arr[left].elapsed < arr[right].elapsed ? left : right;
if (arr[parent].elapsed > arr[smaller].elapsed) {
swap(&arr[parent], &arr[smaller]);
}
else {
break;
}
parent = smaller;
left = parent * 2;
right = parent * 2 + 1;
}
Size--;
}
Heap pq;
int visit[501] = { 0 };
int solution(vector<vector<int>> jobs) {
int answer = 0;
int cur = 0;
sort(jobs.begin(), jobs.end());
cur = jobs[0][0];
int start=0;
for(int j=0;j<jobs.size();j++) {
for (int i = start; i < jobs.size(); i++) {
if (cur >= jobs[i][0] && visit[i] == 0)
{
elem tmp;
tmp.st = jobs[i][0];
tmp.elapsed = jobs[i][1];
pq.push(tmp);
visit[i] = 1;
}
else {
start = i;
break;
}
}
if (pq.empty()) {
elem tmp;
tmp.st = jobs[start][0];
tmp.elapsed = jobs[start][1];
start++;
pq.push(tmp);
}
else {
answer += (pq.front().elapsed + cur - pq.front().st);
cur += (pq.front().elapsed);
pq.pop_front();
}
}
answer /= jobs.size();
return answer;
}
void main() {
vector<int> tmp;
vector<vector<int>> tmp2;
tmp.push_back(1);
tmp.push_back(3);
tmp2.push_back(tmp);
tmp.clear();
tmp.push_back(1);
tmp.push_back(9);
tmp2.push_back(tmp);
tmp.clear();
tmp.push_back(2);
tmp.push_back(6);
tmp2.push_back(tmp);
tmp.clear();
solution(tmp2);
}#include <string>
#include <vector>
#include <iostream>
#include<algorithm>
#define N 500
using namespace std;
struct elem {
int st=-1, elapsed=-1;
};
//최소 힙.
class Heap {
private:
int Size = 0;
elem arr[N * 2 + 1];
public:
void push(elem x);
elem front();
void pop_front();
void swap(elem *a, elem *b);
bool empty();
};
bool Heap::empty() {
if (Size == 0) {
return true;
}
else {
return false;
}
}
void Heap::swap(elem *a, elem*b) {
elem tmp = *a;
*a = *b;
*b = tmp;
}
void Heap::push(elem x) {
int parent;
Size++;
arr[Size] = x;
parent = Size / 2;
if (Size >= 2) {
while (parent != 0 && arr[parent].elapsed > arr[Size].elapsed) {
swap(&arr[parent], &arr[Size]);
parent = parent / 2;
}
}
}
elem Heap::front() {
elem empty;
if (Size >= 0)
return arr[1];
else
return empty;
}
void Heap::pop_front() {
int parent = 1;
int left, right;
swap(&arr[parent], &arr[Size]);
left = parent * 2;
right = parent * 2 + 1;
while (right < Size) {
int smaller = arr[left].elapsed < arr[right].elapsed ? left : right;
if (arr[parent].elapsed > arr[smaller].elapsed) {
swap(&arr[parent], &arr[smaller]);
}
else {
break;
}
parent = smaller;
left = parent * 2;
right = parent * 2 + 1;
}
Size--;
}
Heap pq;
int visit[501] = { 0 };
int solution(vector<vector<int>> jobs) {
int answer = 0;
int cur = 0;
sort(jobs.begin(), jobs.end());
cur = jobs[0][0];
int start=0;
int cnt = jobs.size();
while(cnt) {
for (int i = start; i < jobs.size(); i++) {
if (cur >= jobs[i][0] && visit[i] == 0)
{
elem tmp;
tmp.st = jobs[i][0];
tmp.elapsed = jobs[i][1];
pq.push(tmp);
visit[i] = 1;
}
else {
start = i;
break;
}
}
if (pq.empty()) {
cur = jobs[start][0];
}
else {
answer += (pq.front().elapsed + cur - pq.front().st);
cur += (pq.front().elapsed);
cnt--;
pq.pop_front();
}
}
answer /= jobs.size();
return answer;
}
고친것ㄴ데 왜 틀리는지 모르겠다. 40점인데 뒤에 케이스들만 맞는다. 진짜 이상하다.
아 경과 시간이 같으면? 시작 시간이 빠른게 먼저다. -> 이건 시작 시간순으로 정렬하고 큐에 넣으므로 괜찬다.
찾았다. 힙에 푸쉬가 틀렸었다. 현재 85점
#include <string>
#include <vector>
#include <iostream>
#include<algorithm>
#define N 500
using namespace std;
struct elem {
int st = -1, elapsed = -1;
};
//최소 힙.
class Heap {
private:
int Size = 0;
elem arr[N * 2 + 1];
public:
void push(elem x);
elem front();
void pop_front();
void swap(elem *a, elem *b);
bool empty();
};
bool Heap::empty() {
if (Size == 0) {
return true;
}
else {
return false;
}
}
void Heap::swap(elem *a, elem*b) {
elem tmp = *a;
*a = *b;
*b = tmp;
}
void Heap::push(elem x) {
int parent,child;
Size++;
arr[Size] = x;
parent = Size / 2;
child = Size;
if (Size >= 2) {
while (parent != 0 && arr[parent].elapsed > arr[child].elapsed) {
swap(&arr[parent], &arr[child]);
child = parent;
parent = parent / 2;
}
}
}
elem Heap::front() {
elem empty;
if (Size >= 0)
return arr[1];
else
return empty;
}
void Heap::pop_front() {
int parent = 1;
int left, right;
swap(&arr[parent], &arr[Size]);
left = parent * 2;
right = parent * 2 + 1;
while (right < Size) {
int smaller = arr[left].elapsed < arr[right].elapsed ? left : right;
if (arr[parent].elapsed > arr[smaller].elapsed) {
swap(&arr[parent], &arr[smaller]);
}
else {
break;
}
parent = smaller;
left = parent * 2;
right = parent * 2 + 1;
}
Size--;
}
Heap pq;
int visit[501] = { 0 };
int solution(vector<vector<int>> jobs) {
int answer = 0;
int cur = 0;
sort(jobs.begin(), jobs.end());
cur = jobs[0][0];
int start = 0;
int cnt = jobs.size();
while (cnt) {
for (int i =start; i < jobs.size(); i++) {
if ((cur >= jobs[i][0] && visit[i] == 0) || pq.empty())
{
elem tmp;
tmp.st = jobs[i][0];
tmp.elapsed = jobs[i][1];
pq.push(tmp);
visit[i] = 1;
}
else {
start = i;
break;
}
}
answer += (pq.front().elapsed + cur - pq.front().st);
cur += (pq.front().elapsed);
cnt--;
pq.pop_front();
}
answer /= jobs.size();
return answer;
}
cur >= jobs[i][0] 에서 =를 빼니까 90점이 됬다....아~~!@~!@
아.... priority queue stl로 구현하니까 맞았다...
#include <string>
#include <vector>
#include <iostream>
#include<algorithm>
#include<queue>
#include<functional>
#define N 1000
using namespace std;
struct elem {
int st = -1, elapsed = -1;
};
//최소 힙.
class Heap {
private:
int Size = 0;
elem arr[N * 2 + 1];
public:
void push(elem x);
elem front();
void pop_front();
void swap(elem *a, elem *b);
bool empty();
};
bool Heap::empty() {
if (Size == 0) {
return true;
}
else {
return false;
}
}
void Heap::swap(elem *a, elem*b) {
elem tmp = *a;
*a = *b;
*b = tmp;
}
void Heap::push(elem x) {
int parent, child;
Size++;
arr[Size] = x;
parent = Size / 2;
child = Size;
if (Size >= 2) {
while (parent != 0) {
if (arr[parent].elapsed > arr[child].elapsed) {
swap(&arr[parent], &arr[child]);
child = parent;
parent = parent / 2;
}
else if (arr[parent].elapsed == arr[child].elapsed &&arr[parent].st == arr[child].st) {
swap(&arr[parent], &arr[child]);
child = parent;
parent = parent / 2;
}
}
}
}
elem Heap::front() {
elem empty;
if (Size > 0)
return arr[1];
else
return empty;
}
void Heap::pop_front() {
int parent = 1;
int left, right;
swap(&arr[parent], &arr[Size]);
left = parent * 2;
right = parent * 2 + 1;
while (right < Size) {
int smaller = arr[left].elapsed < arr[right].elapsed ? left : right;
if (arr[left].elapsed < arr[right].elapsed) {
smaller = left;
}
else if (arr[left].elapsed == arr[right].elapsed) {
if (arr[left].st < arr[right].st) {
smaller = left;
}
else {
smaller = right;
}
}
else {
smaller = right;
}
if (arr[parent].elapsed > arr[smaller].elapsed) {
swap(&arr[parent], &arr[smaller]);
}
else {
break;
}
parent = smaller;
left = parent * 2;
right = parent * 2 + 1;
}
Size--;
}
//Heap pq;
bool operator<(elem t, elem u) {
return t.elapsed > u.elapsed;
}
priority_queue<elem> pq;
int visit[501] = { 0 };
int solution(vector<vector<int>> jobs) {
int answer = 0;
int cur = 0;
sort(jobs.begin(), jobs.end());
cur = jobs[0][0];
int start = 0;
int cnt = jobs.size();
while (cnt) {
for (int i = start; i < jobs.size(); i++) {
if ((cur >= jobs[i][0] && visit[i] == 0) || pq.empty())
{
if ((cur > jobs[i][0] && visit[i] == 0)) {
elem tmp;
tmp.st = jobs[i][0];
tmp.elapsed = jobs[i][1];
// cout << "elapsed : " << tmp.elapsed << "\n";
pq.push(tmp);
visit[i] = 1;
}
else {
elem tmp;
tmp.st = jobs[i][0];
tmp.elapsed = jobs[i][1];
// cout << "elapsed : " << tmp.elapsed << "\n";
pq.push(tmp);
visit[i] = 1;
cur = tmp.st;
}
}
else {
start = i;
break;
}
}
/*
answer += (pq.front().elapsed + cur - pq.front().st);
cur += (pq.front().elapsed);
cnt--;
pq.pop_front();
*/
answer += (pq.top().elapsed + cur - pq.top().st);
cur += (pq.top().elapsed);
cnt--;
pq.pop();
}
answer /= jobs.size();
return answer;
}
힙 구현을 더 연습하자. !! -> 링크드 리스트로 구현하자 .ㅠㅠ 자꾸 틀림.아~ 그리고 프로그래머스 문제들이 라인 대비하기 딱 좋은거 같다.
디스크 컨트롤러 다시 했다. 연산자 오버로딩을 사용해서.
#include <string>
#include <vector>
#include <iostream>
#include<algorithm>
#include<queue>
#include<functional>
#define N 1000
using namespace std;
struct elem {
int st = -1, elapsed = -1;
};
//최소 힙.
class Heap {
private:
int Size = 0;
elem arr[N * 2 + 1];
public:
void push(elem x);
elem front();
void pop_front();
void swap(elem *a, elem *b);
bool empty();
};
bool operator > (elem t, elem u) {
return t.elapsed > u.elapsed;
}
bool operator < (elem t, elem u) {
return t.elapsed < u.elapsed;
}
bool Heap::empty() {
if (Size == 0) {
return true;
}
else {
return false;
}
}
void Heap::swap(elem *a, elem*b) {
elem tmp = *a;
*a = *b;
*b = tmp;
}
void Heap::push(elem x) {
int parent, child;
Size++;
arr[Size] = x;
parent = Size / 2;
child = Size;
while (child >= 2 && arr[parent] > arr[child]) {
swap(&arr[parent], &arr[child]);
child = parent;
parent = parent / 2;
}
}
elem Heap::front() {
elem empty;
if (Size > 0)
return arr[1];
else
return empty;
}
void Heap::pop_front() {
int parent = 1;
int left, right;
swap(&arr[parent], &arr[Size]);
Size--;
int smaller = parent*2;
if (smaller + 1 <= Size)
smaller = arr[smaller] < arr[smaller + 1] ? smaller : smaller + 1;
while (smaller <= Size && arr[parent] > arr[smaller]) {
swap(&arr[parent], &arr[smaller]);
parent = smaller;
smaller = 2 * smaller;
if (smaller + 1 <= Size) {
smaller = arr[smaller] < arr[smaller + 1] ? smaller : smaller + 1;
}
}
}
Heap pq;
/*
priority_queue<elem> pq;
*/
int visit[1001] = { 0 };
int solution(vector<vector<int>> jobs) {
int answer = 0;
int cur = 0;
sort(jobs.begin(), jobs.end());
cur = jobs[0][0];
int start = 0;
int cnt = jobs.size();
while (cnt) {
for (int i = start; i < jobs.size(); i++) {
if ((cur >= jobs[i][0] && visit[i] == 0) || pq.empty())
{
if ((cur > jobs[i][0] && visit[i] == 0)) {
elem tmp;
tmp.st = jobs[i][0];
tmp.elapsed = jobs[i][1];
// cout << "elapsed : " << tmp.elapsed << "\n";
pq.push(tmp);
visit[i] = 1;
}
else {
elem tmp;
tmp.st = jobs[i][0];
tmp.elapsed = jobs[i][1];
// cout << "elapsed : " << tmp.elapsed << "\n";
pq.push(tmp);
visit[i] = 1;
cur = tmp.st;
}
}
else {
start = i;
break;
}
}
answer += (pq.front().elapsed + cur - pq.front().st);
// cout << "answer: " << answer << "\n";
cur += (pq.front().elapsed);
//cout << "cur: " << cur << "\n";
cnt--;
pq.pop_front();
}
answer /= jobs.size();
return answer;
}
/*
void main() {
pq.push({ 4,12 });
pq.push({ 0,14 });
pq.push({ 2,5 });
cout << pq.front().elapsed << "\n";
pq.pop_front();
cout << pq.front().elapsed << "\n";
pq.pop_front();
cout << pq.front().elapsed << "\n";
pq.pop_front();
}
*/'알고리즘 문제 풀기' 카테고리의 다른 글
| swexpertacademy - 1768. 숫자야구게임 (0) | 2020.01.08 |
|---|---|
| swexpertacademy - 9088. 다이아몬드,8998. 세운이는 내일 할거야, 8993. 하지 추측 (0) | 2020.01.06 |
| 프로그래머스 - 카카오 2018 블라인드 테스트 (추석 트래픽) (0) | 2020.01.04 |
| 백준 - 1725번 히스토그램,6549 히스토그램에서 가장 큰 직사각형 (0) | 2020.01.03 |
| 프로그래머스 - 카카오 2020 블라인드 테스트 (블록 이동하기, 문자열 압축) (0) | 2020.01.02 |