[BOJ] 백준 3217 malloc

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

 Input 

5

baka=malloc(214);

baka=malloc(123);

free(baka);

deda=malloc(100);

print(deda);

 

 Output 

215

 

주어지는 명령에서 변수는 항상 4글자 소문자 이므로

특정 위치의 문자를 확인해서 명령이 무엇인지 확인할 수 있습니다.

(모든 명령은 최소 6글자 이상을 보장합니다.)

- 5번째 글자가 『 = 』 → xxxx=malloc(size);

- 5번째 글자가 『 ( 』 → free(var);

- 6번째 글자가 『 ( 』 → print(var);

 

- 시작 번호와 할당가능한 크기를 나타내는 free block

- 각 변수에 할당된 메모리 (시작 번호 + 할당된 크기)

  (변수에 저장된 메모리 정보를 Hash Table로 저장)

 

시뮬레이션

[초기] 시작번호 = 1 사용가능한 메모리 총량 = 100

『1』 에서 공간 크기 100 할당 가능

 

① aaaa=malloc(10) 

『11』 에서 공간 크기 90 할당 가능

 

② bbbb=malloc(30)

『41』 에서 공간 크기 60 할당 가능

 

③ cccc=malloc(20)

『61』 에서 공간 크기 40 할당 가능

 

④ dddd=malloc(5)

『66』 에서 공간 크기 35 할당 가능

중간에 할당한 메모리를 free하지 않고 계속해서 메모리만 할당한다면

메모리 크기가 여유롭다면 위와 같은 방식으로 메모리가 모두 소진될 때까지 새롭게 할당하면 될것입니다.

하지만, 중간에 free하는 경우가 발생했을 때, 이를 어떻게 관리할지 고민해야 합니다.

(왜냐하면 앞선 번호부터 연속된 메모리 공간에 할당해야 하기 때문입니다.)

 

⑤ free(bbbb)

- 『11』 에서 공간 크기 30 할당 가능

- 『66』 에서 35 공간 크기 할당 가능

빈 공간은 30 + 35 = 75이지만 연속된 공간이 아니기 때문에 위와 같이 구현

( 『11』 부터 공간 가능한 크기 30이 앞서므로 앞쪽에 위치합니다.)

 

if) 메모리 공간 33만큼 새롭게 할당한다면?

    현재 빈 메모리 공간은 30 + 35 = 65 → 65 > 33 이므로 파편하된 공간에서 33공간할당이 가능한 곳을 찾습니다.

    『11』 번째는 30만큼 할당가능하므로 넘어갑니다. 이제 탐색하면서 남은 공간(remain)은 35만큼 남아 있습니다.

    『66』 번째에서 35 > 33 이므로 공간 할당이 가능합니다.

if) 메모리 공간 70만큼 새롭게 할당한다면?

    모든 빈공간들을 합쳐도 30 + 35 = 65 → 65 < 70 이므로 할당 불가 (탐색과정 불필요)

if) 메모리 공간 40만큼 새롭게 할당한다면?    

    빈 공간 = 30 + 35 = 65 → 65 > 40 이므로 할당 가능한 곳을 탐색합니다.

    『11』 번째는 30만큼 할당가능한데 40이 필요하므로 pass → 남은 빈 공간(remain) = 70 - 30 = 35

    『66』 번째에서 35 < 40 이므로 할당 불가능 → 남은 빈 공간(remain) = 35 - 35 = 0

    즉, 전체 빈 공간은 40보다 크지만 파편화 되어 있기에 연속된 공간이 없는 상황입니다.

 

⑥ free(cccc)

 

위와 같이 구현할 수도 있지만 『11』 번째부터 크기 50이 남아 있지만, 한번에 확인하기 쉽지 않습니다.

즉, 『11』번째 부터 크기 30과  『41』번째 부터 크기 20을 한번에 표시해야 합니다.

11 + 30 = 41이 되는 상황으로 아래와 같이 표현 가능합니다.

 

⑦ free(dddd)

- 『11』 에서 공간 크기 50 할당 가능

- 『61』 에서 공간 크기 5 할당 가능

- 『66』 에서 공간 크기 35 할당 가능

결과적으로 『11』 에서 공간 크기 50+5+35 = 90 할당 가능

이를 『11』 + 50 = 『61』 이면서 『61』 + 5 = 『66』 인 것으로 모두 연속된것을 알 수 있습니다.

결과적으로 아래와 같이 표현할 수 있습니다.

 

⑨ free(aaaa)

반납 메모리 『1』 + 10 = 『11』 로  『1』 부터 공간 크기 100이 남는것을 위와 같이 표현

(코드에서 free될 때, 어떤 조건으로 분기되며, 연결리스트가 제어되는지 확인 필요)

---

#include <stdio.h>
#include <stdlib.h>
 
const int MAX_N = 1e5;
// 26개 알파벳으로 이루어진 4글자
const int hashSize = 26 * 26 * 26 * 26;
int N, totalSize; // 할당 가능한 크기
typedef struct node{
    int s, size; // 시작 번호, 크기
    struct node* next;
}BLOCK;
BLOCK freeBlock; // 더미노드
BLOCK* varTable[hashSize + 10];
 
int getKey(char* str) {
    int hash = 0;
    for (int i = 0; i < 4; i++) {
        hash = hash * 26 + (str[i] - 'a');
    }
    return hash;
}
 
int getSize(char* str) {
    int size = 0;
    while ('0' <= *str && *str <= '9') {
        size = size * 10 + (*str - '0');
        str++;
    }
    return size;
}
 
void deleteFreeBlock(BLOCK* p){
    if (!p->next) return;
    deleteFreeBlock(p->next);
    free(p->next);
}
 
void allFree(void){
    for (int i = 1; i <= hashSize; i++){
        if (varTable[i] != NULL){
            free(varTable[i]);
            varTable[i] = NULL;
        }
    }
    deleteFreeBlock(&freeBlock);
}
 
void init(){
    freeBlock.next = (BLOCK*)calloc(1, sizeof(BLOCK));
    freeBlock.next->s = 1;
    freeBlock.next->size = MAX_N; // (초기) 할당가능한 크기
    totalSize = MAX_N;
    for (int i = 1; i <= hashSize; i++){
        varTable[i] = NULL;
    }
}
 
void input() {
    scanf("%d", &N);
}
 
BLOCK* myMalloc(int size){
    BLOCK* p = &freeBlock;
    BLOCK* allocBlock;
    // 할당불가능한 크기인 경우
    if (totalSize < size) return NULL;
 
    int remain = totalSize; 
    // 메모리들이 파편화 되어 있을 수 있기에 탐색하면서 남은 용량 확인
    while (p->next && (remain >= size)){
        if (p->next->size == size){
            allocBlock = p->next;
            p->next = allocBlock->next; // p->next->next
            allocBlock->next = NULL;
            totalSize -= size;
            return allocBlock;
        }
        if (p->next->size > size){
            allocBlock = (BLOCK*)calloc(1, sizeof(BLOCK));
            allocBlock->s = p->next->s;
            allocBlock->size = size;
            allocBlock->next = 0;
            p->next->s += size;
            p->next->size -= size;
            totalSize -= size;
            return allocBlock;
        }
        remain -= p->next->size;
        p = p->next;
    }
    return NULL;
}
 
void myFree(BLOCK* target){
    BLOCK* p = &freeBlock;
    // 할당한 적 없는 변수인 경우
    if (target == NULL) return;
    
    totalSize += target->size;
    // 빈 공간이 남아 있지 않아서 새로 추가되는 경우
    if (p->next == NULL){
        p->next = target;
        return;
    }
 
    while (p->next){
        // 반납하는 메모리가 연속적으로 이어지지 않는 경우
        if (target->s + target->size < p->next->s){
            target->next = p->next;
            p->next = target;
            return;
        }
        // 시작할 때 위의 조건에서 return 하지 않은 경우
        // target 보다 앞에 위치한 free block 공간으로 계산 필요
        p = p->next;
 
        // 메모리를 반납해서 연속 구간으로 이어지는 경우
        if (target->s + target->size == p->s){
            p->s = target->s;
            p->size += target->size;
            return;
        }
 
        // 빈 공간의 끝지점의 메모리가 반납되는 경우
        if (target->s == p->s + p->size){
            p->size += target->size;
            if (p->next && (p->next->s == p->s + p->size)){
                p->size += p->next->size;
                p->next = p->next->next;
            }
            return;
        }
    }
}
 
void solve(void){
    char cmd[100];
    int size, key;
    for (int i = 1; i <= N; i++){
        scanf("%s", cmd);
        if (cmd[4] == '='){ // malloc
            key = getKey(cmd); // hash key
            size = getSize(cmd + 12); // 할당 크기
            varTable[key] = myMalloc(size);
        }
        else if (cmd[4] == '('){ // free
            key = getKey(cmd + 5);
            myFree(varTable[key]);
            varTable[key] = NULL;
        }
        else{ // print
            key = getKey(cmd + 6);
            if (varTable[key] == NULL) printf("0\n");
            else printf("%d\n", varTable[key]->s);
        }
    }
}
 
int main(void){
    // freopen("input.txt", "r", stdin);
    init();
    input();
    solve();
    allFree(); // 할당한 메모리 모두 free
}