BOJ 3217 malloc

BOJ 3217 malloc

[분류 : 구현 / 세그먼트 트리]

  최대 변수의 개수는 1000개, 또 메모리 할당 범위는 100 <= size <= 100000, 사용 가능한 메모리 크기는 100000이므로 최대 1000개의 범위 구간이 메모리에 존재할 수 있다.

[풀이 1] 단순 구간 저장
  할당된 구간의 범위를 저장하고, malloc 명령으로 메모리를 할당할 때는 그 사이에 있는 값(할당되지 않은 메모리) 중 size보다 크거나 같은 값을 반환토록 한다. 최악의 경우 O(1000 * N) = O(10^8)까지 올라가지만 아슬아슬하게 1초 내에 쿼리에 답할 수 있어보인다(하지만 최악의 테케가 없는 것 같음).

 

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5;
int main() {
    char cmd[100];
    map<string, list<pair<int, int>>::iterator> addr;
    string var, sz;
    int N, _sz;

    list<pair<int, int>> allocated;
    allocated.push_back({ 1, 1 });
    allocated.push_back({ MAX_N + 1, MAX_N + 1 });

    scanf("%d", &N);
    while (N--) {
        scanf("%s", cmd);
        if (cmd[4] == '=') {
            var = string(cmd).substr(0, 4);
            addr.erase(var);

            sscanf(cmd + 12, "%d", &_sz);

            auto nxt = allocated.begin();
            auto cur = nxt++;
            while (nxt != allocated.end()) {
                if (nxt->first - cur->second >= _sz)
                    break;
                cur++, nxt++;
            }
            if (nxt == allocated.end())
                continue;
            else
                addr[var] = allocated.insert(nxt, { cur->second, cur->second + _sz });
        }
        else {
            var = string(cmd).substr(cmd[0] == 'p' ? 6 : 5, 4);

            auto it = addr.find(var);
            if (cmd[0] == 'p')
                printf("%d\n", it == addr.end() ? 0 : it->second->first);
            else {
                if (it != addr.end()) {
                    allocated.erase(it->second);
                    addr.erase(it);
                }
            }
        }
    }
    return 0;
}

 

---

 

[풀이 2] 레이지 세그먼트 트리
  [세그 트리 구성] 각 세그 노드는 아래와 같은 데이터를 갖는다.

lv = {정수, 가장 왼쪽부터 시작해서 연속해서 사용 가능한 메모리의 길이}    rv = {정수, 가장 오른쪽부터 시작해서 연속해서 사용 가능한 메모리의 길이}    mv = {정수, 해당 노드가 포함하는 구간 내에서 가장 긴 연속해서 사용 가능한 메모리의 길이}

 

  이 상태에서 부모 노드가 자식 노드로부터 데이터를 모을 때는 아래처럼 건설해나가면 된다.

/*
 * p_node : 부모 노드 
 * left_node : 왼쪽 자식 노드 
 * right_node : 오른쪽 자식 노드
 */
p_node.lv = left_node.lv + (만약 left_node 범위의 크기와 left_node.lv가 같다면 right_node.lv를 더해주고 아니면 0을 더해준다.)
p_node.rv = right_node.rv + (만약 right_node 범위의 크기와 right_node.rv가 같다면 left_node.rv를 더해주고 아니면 0을 더해준다.)
p_node.mv = max(p_node.lv, p_node.rv, left_node.mv, right_node.mv, left_node.rv + right_node.lv)

  현재 노드의 최대 값 mv를 계산할 때 범위 가운데에 있는 값도 고려해야 하는 점을 눈여겨 보자.

  [쿼리] 현재 상태에서 쿼리를 날리면 그냥 메모리에 size만큼 할당 가능한지 안한지를 아는 것 밖에 못한다. 구간의 mv 값을 확인하면 바로 확인 가능하기 때문인데, 이는 문제에서 요구하는 가능한 주소 중 가장 작은 주소를 알 수 없다.
따라서 그리디하게 왼쪽 자식부터 시작해서 '왼쪽 자식 -> 왼쪽 자식과 오른쪽 자식을 합치는 경우 -> 오른쪽 자식' 순으로 메모리 할당 구간을 검색하며 주소값을 반환하도록 하면 된다.

query(size) : 메모리 할당이 가능하면 최소 주소값을 반환한다. 아니면 유효하지 않은 값을 반환한다.       (1) 왼쪽 자식 노드 구간으로만 size를 가지고 있으면 왼쪽 자식의 값을 반환한다.       (2) 왼쪽 자식 노드의 rv와 오른쪽 자식 노드의 lv를 합친 값이 size를 만족하면 '중간 위치 - rv + 1'를 반환한다.      (3) 오른쪽 자식의 값을 반환한다.

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
const int MAX_N = 1 << 17, INF = 1e9, LIMIT = 1e5;
struct _d { int mv, lv, rv; } t[(MAX_N + 1) * 2 + 1];
int n = LIMIT, lazy[(MAX_N + 1) * 2 + 1];
void push(int idx, int L, int R) {
	if (lazy[idx] == -1) return;
	int d = lazy[idx];
	t[idx].lv = t[idx].rv = t[idx].mv = d ? R - L + 1 : 0;
	if (L != R) {
		lazy[idx << 1] = d;
		lazy[idx << 1 | 1] = d;
	}
	lazy[idx] = -1;
}
void update(int idx, int L, int R, int l, int r, int d) {
	push(idx, L, R);
	if (r < L || R < l) return;
	if (l <= L && R <= r) {
		lazy[idx] = d;
		push(idx, L, R);
		return;
	}
	int m = (L + R) >> 1;
	update(idx << 1, L, m, l, r, d);
	update(idx << 1 | 1, m + 1, R, l, r, d);
	_d& tl = t[idx << 1], & tr = t[idx << 1 | 1], & tc = t[idx];
	tc.lv = tl.lv + (tl.lv == m - L + 1 ? tr.lv : 0);
	tc.rv = tr.rv + (tr.rv == R - m ? tl.rv : 0);
	tc.mv = max({ tc.lv, tc.rv, tl.rv + tr.lv, tl.mv, tr.mv });
}
int query(int idx, int L, int R, int l, int r, int req) {
	push(idx, L, R);
	if (r < L || R < l) return -1;
	if (t[idx].mv < req) return -1;
	if (L == R)
		return L;
	int m = (L + R) >> 1;
	push(idx << 1, L, m), push(idx << 1 | 1, m + 1, R);
	_d& tl = t[idx << 1], & tr = t[idx << 1 | 1];
	if (tl.mv >= req) return query(idx << 1, L, m, l, r, req);
	else if (tl.rv + tr.lv >= req) return m - tl.rv + 1;
	else return query(idx << 1 | 1, m + 1, R, l, r, req);
}
void update(int l, int r, int d) { update(1, 0, n - 1, l, r, d); }
int query(int req) { return query(1, 0, n - 1, 0, n - 1, req); }

int main() {
	memset(lazy, -1, sizeof lazy);

	char cmd[100];
	map<string, pair<int, int>> addr;
	string var;
	int N, _sz, l, i;
	update(0, n - 1, 1);

	scanf("%d", &N);
	while (N--) {
		scanf("%s", cmd);
		if (cmd[4] == '=') {
			var = string(cmd).substr(0, 4);
			addr.erase(var);

			sscanf(cmd + 12, "%d", &_sz);

			l = query(_sz);
			if (l == -1) addr[var] = { -1, 0 };
			else {
				addr[var] = { l, _sz };
				update(l, l + _sz - 1, 0);
			}
		}
		else {
			var = string(cmd).substr(cmd[0] == 'p' ? 6 : 5, 4);
			if (addr.find(var) == addr.end())
				addr[var] = { -1, 0 };
			if (cmd[0] == 'p')
				printf("%d\n", addr[var].first + 1);
			else {
				if (addr[var].first != -1) {
					l = addr[var].first;
					_sz = addr[var].second;
					update(l, l + _sz - 1, 1);
					addr[var] = { -1, 0 };
				}
			}
		}
	}
	return 0;
}