[G1] 백준 3217번 malloc C++ 구현, 연결 리스트, 해시맵, 문자열

리뷰

 

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

이 문제 덕분에 malloc의 작동 방식에 대해 더욱 깊게 알게 되었다.

 

 

전역 변수

• M : 메모리 최대값의 크기를 정의할 상수 변수
• n : 명령의 개수를 저장할 변수
• Node : 연결 리스트의 노드를 정의할 구조체
• dic : 각 변수가 할당된 노드 포인터를 저장할 해시맵

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, 임의의 root노드를 한개 생성해 준다.
2. n번의 while루프를 수행하고, 변수 q에 각 명령에 해당하는 문자열을 입력 받아준다.
3. 모든 명령엔 괄호안에 인자가 주어지므로 변수 inner에 인자를 문자열로 저장해 준다.
4. malloc명령이 주어질 경우 변수 var에 변수명을 문자열로 입력 받아주고, 변수 size에 inner를 정수로 바꿔 저장한다.
5. Node포인터 변수 cur에 root를 저장하고, 무한 루프를 수행해 준다.
6. cur이 마지막 노드 이면서 할당 후 메모리의 끝이 M보다 작을경우 노드를 맨끝에 삽입해 준다.
7. 만약 노드를 할당할 수 없는 경우 dic[var]을 nullptr로 저장해 준다.
8. cur이 중간 노드지만 동적 할당해 줄 공간이 있을 경우 노드를 삽입해 준다.
9. 위 두 케이스에 맞는 삽입 위치가 나올 때 까지 연결리스트를 순회해 준다.
10. print명령이 주어질 경우 dic에 inner가 없거나 값이 nullptr일 경우 0을, 아니라면 노드의 st값을 출력한다.
11. free명령이 주어질 경우 dic에 inner가 없거나 값이 nullptr일 경우 continue를, 아니라면 현재 노드를 삭제한다.

 

트러블 슈팅

1. 해시맵의 키를 변수명, 값을 vector<Node*>로 구현하여 중복 free호출 시 순차적으로 지워주는 로직을 작성하였다.
2. 동일한 변수에 malloc명령이 추가로 인입된 경우 해당 값으로 덮어써주어 AC를 받았다.

 

참고 사항

1. malloc은 연속된 메모리 구조를 가질 필요 없이 할당할 수 있는 메모리 공간만 있으면 할당할 수 있다.
2. 동일한 변수에 malloc을 추가로 진행할 경우 이전에 동적할당한 메모리를 해제할 수 없어 누수가 발생한다.

 

정답 코드

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

const int M = 1e5;
int n;

struct Node {
	string var;
	int st, ed;
	Node* prev;
	Node* next;

	Node(string VAR, int ST, int ED) : var(VAR), st(ST), ed(ED), prev(nullptr), next(nullptr) {}
};
unordered_map<string, Node*> dic;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	Node* root = new Node("root", 0, 0);

	while (n--) {
		string q; cin >> q;
		auto it1 = find(q.begin(), q.end(), '(');
		auto it2 = find(q.begin(), q.end(), ')');
		string inner = string(it1 + 1, it2);

		if (q.find("malloc") != string::npos) {
			string var = string(q.begin(), q.begin() + 4);
			int size = stoi(inner);
			
			Node* cur = root;
			while (1) {
				if (cur->next == nullptr) {
					//cout << cur->var << " " << cur->st << " " << cur->ed << "\n";
					int st = cur->ed + 1;
					int ed = cur->ed + size;

					if (ed <= M) {
						Node* node = new Node(var, st, ed);
						node->prev = cur;
						cur->next = node;
						dic[var] = node;
					}
					else dic[var] = nullptr;
					break;
				}

				int st = cur->ed + 1;
				int ed = cur->ed + size;
				//cout << cur->var << " " << cur->st << " " << cur->ed << " " << cur->next->var << " " << cur->next->st << " " << cur->next->ed << "\n";
				if (ed < cur->next->st) {
					Node* node = new Node(var, st, ed);

					node->next = cur->next;
					node->next->prev = node;

					node->prev = cur;
					cur->next = node;

					dic[var] = node;
					break;
				}
				cur = cur->next;
			}
		}
		else if (q.find("print") != string::npos) {
			auto it = dic.find(inner);
			if (it == dic.end() || !it->second) cout << 0 << "\n";
			else cout << it->second->st << "\n";
		}
		else {
			auto it = dic.find(inner);
			if (it == dic.end() || !it->second) continue;
			else {
				Node* node = it->second;

				if (node->next != nullptr) {
					node->prev->next = node->next;
					node->next->prev = node->prev;
				}
				else node->prev->next = nullptr;

				it->second = nullptr;
				delete node;
			}
		}
	}
}