[백준/BOJ] 백준 16347번 : Alloc

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

16347번: Alloc

리스트에 빈 공간의 메모리 위치와 해당 메모리 위치에서 할당이 가능한 크기를 저장하여, 메모리 할당을 할 때는 할당하는 메모리만큼 리스트에서 적절한 빈 공간을 찾아서 빈 공간의 크기를 줄여 메모리를 할당하고, 할당한 변수에 대한 이름과 메모리 정보를 저장해 두었다. 만약 딱 맞는 빈 공간을 찾아 빈 공간의 크기를 줄였을 때 남은 빈 공간이 없어졌다면 리스트에서 지웠다. 또한 할당한 메모리를 해제할 때 리스트를 확인하면서 적절한 위치를 찾아 해당 위치에 빈 공간을 추가하고, 추가한 빈 공간이 앞 또는 뒤 빈 공간과 연속적인 공간으로 되어 합쳐지는지 확인하는 방식을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <unordered_map>
using namespace std;

list<pair<int, int>> li; //(메모리 위치, 해당 메모리 위치에서 할당 가능한 크기)
list<pair<int, int>>::iterator it;
unordered_map<string, pair<int, int>> var_info; //(변수 이름, (메모리 위치, 할당한 크기))
int n;
vector<int> result;

void Pre()
{
	li.push_back(make_pair(1, 100000)); //초기에는 1번 메모리 위치에 100000만큼의 메모리 공간이 있다
}

void MList(string var, int var_size)
{
	bool add = false;
	for (it = li.begin(); it != li.end(); it++)
	{
		//할당할 수 있는 공간을 찾았을때
		if ((*it).second >= var_size)
		{
			if (var_info.count(var) == 0)
				var_info.insert(make_pair(var, make_pair((*it).first, var_size))); //var변수를 어느 메모리 위치에 얼만큼 할당했는지 저장
			else
				var_info[var] = make_pair((*it).first, var_size);

			int remain_size = (*it).second - var_size; //해당 공간에 할당하고 남는 크기
			int remain_point = (*it).first + var_size; //해당 공간에 할당하고 남은 크기의 해당 메모리 위치

			//할당하고 남는 크기가 없을떄
			if (remain_size == 0)
				li.erase(it);

			else
			{
				(*it).first = remain_point;
				(*it).second = remain_size;
			}

			add = true;
			break;
		}
	}

	//해당 var를 메모리에 할당할 수 없을때
	if (add == false)
	{
		if (var_info.count(var) == 0)
			var_info.insert(make_pair(var, make_pair(0, 0)));
		else
			var_info[var] = make_pair(0, 0);
	}
}

void FList(string var)
{
	int var_point = var_info[var].first;
	int var_size = var_info[var].second;

	//이미 0일때
	if (var_point == 0)
		return;

	bool check = false;
	for (it = li.begin(); it != li.end(); it++)
	{
		//var변수의 위치를 찾았을때
		if (var_point < (*it).first)
		{
			li.insert(it, make_pair(var_point, var_size));

			list<pair<int, int>>::iterator here_it = it;
			here_it--; //here_it은 새로 free되어서 생긴 공간의 위치

			//뒤에 메모리 공간이랑 합쳐지는지 확인
			if (var_point + var_size == (*it).first)
			{
				(*here_it).second += (*it).second;

				//합쳐져서 없어진것은 삭제
				li.erase(it);
			}

			//앞에 메모리 공간이랑 합쳐지는지 확인
			if (here_it != li.begin())
			{
				it = here_it;
				it--;

				//앞에거랑 합쳐질때
				if ((*it).first + (*it).second == (*here_it).first)
				{
					(*it).second += (*here_it).second;

					//합쳐서 없어진것은 삭제
					li.erase(here_it);
				}

			}

			var_info[var].first = 0;
			var_info[var].second = 0;

			check = true;
			break;
		}
	}

	//제일 마지막 위치에 들어가야 할때
	if (check == false)
	{
		li.push_back(make_pair(var_point, var_size));

		list<pair<int, int>>::iterator here_it = li.end();
		here_it--;

		//앞에 메모리 공간이랑 합쳐지는지 확인
		if (here_it != li.begin())
		{
			it = here_it;
			it--;

			//앞에거랑 합쳐질때
			if ((*it).first + (*it).second == (*here_it).first)
			{
				(*it).second += (*here_it).second;

				//합쳐서 없어진것은 삭제
				li.erase(here_it);
			}

		}

		var_info[var].first = 0;
		var_info[var].second = 0;

	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> n;

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

		//malloc일때
		if (input[4] == '=')
		{
			string var = input.substr(0, 4);
			int index1 = input.find("(");
			int index2 = input.find(")");
			int var_size = stoi(input.substr(index1 + 1, index2 - (index1 + 1)));

			MList(var, var_size);
		}

		//free일때
		else if (input[0] == 'f')
		{
			int index1 = input.find("(");
			int index2 = input.find(")");
			string var = input.substr(index1 + 1, index2 - (index1 + 1));

			FList(var);
		}

		//print일때
		else
		{
			int index1 = input.find("(");
			int index2 = input.find(")");
			string var = input.substr(index1 + 1, index2 - (index1 + 1));

			if (var_info.count(var) == 0)
				result.push_back(0);
			else
				result.push_back(var_info[var].first);
		}
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << "\n";

	return 0;
}