[BOJ] 3217 - malloc

https://www.acmicpc.net/problem/3217

BOJ - malloc

문제 유형: 구현, 집합과 맵(set, map), 문자열 처리

문제 난이도: Gold I

시간 제한: 1초

메모리 제한: 128MB

 

문제

메모리 할당 명령을 시뮬레이팅하는 프로그램을 작성하시오.

메모리는 100,000개의 연속된 공간이고, 1번부터 100,000번까지 번호가 매겨져 있다. 초기에 모든 공간은 할당되지 않은 상태이다.

명령어의 종류는 다음 중 하나이다.

1. var=malloc(size);
   • 이 함수은 처음 등장하는 size개의 연속된 공간을 찾아, 할당해주는 함수이다. 이 함수의 리턴값은 할당된 공간의 제일 처음 주소이다. 만약, 할당해줄 수 있는 공간이 없다면 0을 리턴한다. (100 ≤ size ≤ 100,000)
2. free(var);
   • 이 함수는 이전에 malloc을 통해 var에 할당된 공간을 할당 해제시켜주고, var에 0을 저장하는 함수이다. 만약, var가 이미 0이라면, 아무 일도 일어나지 않는다.
3. print(var);
   • var에 저장된 값을 출력하는 함수이다.

모든 명령은 세미콜론(';')으로 끝난다. 변수는 알파벳 소문자로 이루어져 있으며, 항상 네글자이다. 서로 다른 변수의 개수는 1,000개보다 작거나 같다. 모든 변수는 0으로 초기화되어있다.

 

입력

첫째 줄에 명령의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개의 줄에는 명령이 수행된 순서대로 하나씩 주어진다.

print는 한 번 이상 주어진다.

 

출력

print가 나올 때 마다 결과를 한 줄에 하나씩 출력한다.

 

풀이

우선, 명령어를 파싱을 구현해야 한다.

명령어의 4번인덱스에  '='가 있다면, malloc,

5번인덱스에 '('가 있다면, print,

4번인덱스에 '('가 있다면 free이다.

 

변수의 값을 추적하기 위해, 해시맵을 이용한다. varVals[var] = {시작주소, 크기}를 저장한다.

그리고, 메모리 관리를 위해, {1, 100000}, 즉, start, end꼴의 빈 메모리 블럭을 freeBlocks라는 set에 넣는다.

 

이제, 각 명령어를 받아서 파싱하여 실행하면 된다.

malloc의 실행은, set에 있는 빈 메모리 블록들 중에서, 이번 메모리 할당을 감당할 수 있는 최초의 블록을 찾는다.

  이 메모리 블록에서 필요한 부분만큼 앞에를 떼서 사용한다고 보면 된다. 남은 메모리 블록의 {start, end}스펙만큼 set에 다시 넣는다.

print의 실행은, 해시맵에 저장되어있는 시작주소 값을 출력하면 끝이다.

free의 실행은, 이진 탐색으로 새로운 빈 메모리 블록을 끼울 곳을 찾는 것이다.

  그 뒤, 양쪽에 있는 빈 메모리 블록과 병합을 시도한다.

병합된 빈 메모리 블록을 set에 다시넣어주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

struct result {
    int size;
    string var;
    string cmd;

    result(int size, string& var, string& cmd) {
        this->size = size;
        this->var = var;
        this->cmd = cmd;
    }
};

result parse(string& s) {
    string var = "";
    string cmd = "";
    if (s[4] == '=') {
        int i = 12;
        cmd = "malloc";
        var = s.substr(0, 4);
        string sz = "";
        while (i < s.size() && s[i] != ')') {
            sz += s[i++];
        }
        int size = stoi(sz);

        return result(size, var, cmd);
    } else if (s[5] == '(') {
        var = s.substr(6, 4);
        cmd = "print";

        return result(0, var, cmd);
    } else if (s[4] == '(') {
        var = s.substr(5, 4);
        cmd = "free";

        return result(0, var, cmd);
    }

    return result(-1, var, cmd);
}

int allocate(int sz, set<pii>& freeBlocks) {
    for (auto it = freeBlocks.begin(); it != freeBlocks.end(); it++) {
        int l = it->first, r = it->second;
        int len = r - l + 1;
        if (len >= sz) {
            int addr = l;
            int newL = l + sz;
            freeBlocks.erase(it);
            if (newL <= r) freeBlocks.insert({newL, r});
            return addr;
        }
    }

    return 0;
}

void deallocate(int addr, int sz, set<pii>& freeBlocks) {
    int l = addr, r = addr + sz - 1;
    auto it = freeBlocks.lower_bound({l, r});
    // merge left
    if (it != freeBlocks.begin()) {
        auto prev = it;
        --prev;
        if (prev->second + 1 >= l) {
            l = prev->first;
            r = max(r, prev->second);
            freeBlocks.erase(prev);
        }
    }

    // merge right
    while (it != freeBlocks.end() && it->first <= r + 1) {
        l = min(l, it->first);
        r = max(r, it->second);
        auto nxt = next(it);
        freeBlocks.erase(it);
        it = nxt;
    }
    freeBlocks.insert({l, r});
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    unordered_map<string, pii> varVals;
    set<pii> freeBlocks;
    freeBlocks.insert({1, 100000});

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        auto res = parse(s);
        if (res.cmd == "malloc") {
            int addr = allocate(res.size, freeBlocks);
            varVals[res.var] = {addr, (addr == 0 ? 0 : res.size)};
        } else if (res.cmd == "print") {
            cout << varVals[res.var].first << "\n";
        } else if (res.cmd == "free") {
            auto [addr, sz] = varVals[res.var];
            if (addr != 0) {
                deallocate(addr, sz, freeBlocks);
                varVals[res.var] = {0, 0};
            }
        }
    }

    return 0;
}