2214
unknown
plain_text
7 months ago
3.9 kB
0
Indexable
Never
// [My 풀이방법] // allocate, release 총 command 수가 30,000 이기 때문에 O(1) 이나 O(logN) 에 각 api 를 처리 해야된다. // allocate 시 가장 적합한 크기의 free area 를 찾아야 하는데 선행탐색으로는 time 아웃 각이다. // 만약 크기 순으로 정렬이 되어 있다면 binary search 로 가능하다 이것을 지원하는 구조가 set 구조이다. // set 의 하한값 lower bound : 같거나 큰값중 가장 작은값 을 이용하면 간단하게 해결 된다. // // release 시에서 address 순으로 정렬이 되어 있다면 앞/뒷 비교하여 합칠수 있다면 합친다. // 이또한 set 구조를 이용하면 쉽게 해결 가능한다. // // allocate,release 시 같은 set 으로 사용할 수 없기 때문에 각각 만들고 함께 update 해야 된다. // allocate 된 메모리는 hash 형태로 저장하면 O(1) 를 해결 가능하다. // 이렇게 하면 전체적으로 O(NlogN) 으로 해결 가능하다. // #include <set> #include <unordered_map> using namespace std; struct MEM { int addr; int size; bool operator < (const MEM &b)const { if (size != b.size) return size < b.size; return addr < b.addr; } bool operator > (const MEM &b) const { if(addr != b.addr)return addr < b.addr; return size < b.size; } }; set <MEM> fmem; // size 작은순 + addr allocate 시 접합한 size 찾을때 set <MEM, greater<MEM>> famem; // addr 작은순 release 시 앞뛰 merge 여부 확인하기 위함. unordered_map <int, int >amem; // alloc mem addr size void init(int N) { fmem.clear(); famem.clear(); amem.clear(); fmem.insert({ 0,N }); famem.insert({ 0,N }); } int allocate(int mSize) { auto it = fmem.lower_bound({ 0,mSize }); if (it == fmem.end()) return -1; int ret = it->addr; amem[it->addr] = mSize; if (it->size - mSize > 0) { fmem.insert({ it->addr + mSize, it->size - mSize }); famem.insert({ it->addr + mSize, it->size - mSize }); } famem.erase({ it->addr, it->size }); fmem.erase(it); return ret; } int release(int mAddr) { if (amem.find(mAddr) == amem.end()) return -1; MEM f; int ret; f.addr = mAddr; ret =f.size = amem[mAddr]; amem.erase(mAddr); // alloc 에서 삭제 auto it = famem.insert(f); fmem.insert(f); // 뒤쪽과 합칠수 있는지 확인하고 합친다. auto nx = next(it.first); if (nx != famem.end()) { // free 해서 집어넣은 mem와 뒷부분 merge 가능하면 if (it.first->addr + it.first->size == nx->addr) { auto tmp =famem.insert({ it.first->addr,it.first->size + nx->size }); // 합쳐 하나로 만들어 넣고 fmem.insert({ it.first->addr,it.first->size + nx->size }); fmem.erase({ it.first->addr,it.first->size }); famem.erase(it.first); // 기존에 있는 부분 삭제 fmem.erase({ nx->addr,nx->size }); famem.erase(nx); it = tmp; } } // 앞쪽과 합칠수 있으면 확인하고 합친다. auto pr = prev(it.first); if (pr != famem.end()) { if (pr->addr + pr->size == it.first->addr) { famem.insert({ pr->addr,pr->size + it.first->size }); // 합쳐 하나로 만들어 넣고 fmem.insert({ pr->addr,pr->size + it.first->size }); fmem.erase({ it.first->addr,it.first->size }); famem.erase(it.first); // 기존에 있는 부분 삭제 fmem.erase({ pr->addr,pr->size }); famem.erase(pr); } } return ret; }
Leave a Comment