메모리 할당 시뮬레이터

시간 제한1초메모리 제한128 MB

요약
10만 개의 메모리 셀에서 first-fit 방식으로 malloc, free, print 명령을 처리하며 변수별 할당 상태를 시뮬레이션합니다.
난이도

보통10점 중 6점

유형
시뮬레이션, 구현, 정렬
정답자
아직 제출이 없습니다

문제

메모리 할당 명령을 순서대로 실행하는 프로그램을 작성하시오.

메모리는 100,000개의 연속된 칸으로 이루어져 있고, 주소는 1부터 100,000까지이다. 처음에는 모든 칸이 비어 있다.

명령은 다음 세 가지 중 하나이다.

  1. var=malloc(size);
    • 비어 있는 칸 중에서 주소가 가장 작은 위치부터 시작하는, 길이 size의 연속 구간을 찾는다. 찾으면 그 구간을 할당하고 시작 주소를 var에 저장한다. 그런 구간이 없으면 0을 저장한다. (100 ≤ size ≤ 100,000)
    • var에 이미 다른 주소가 들어 있어도, 기존 할당은 자동으로 해제되지 않는다.
  2. free(var);
    • var가 이전에 성공한 malloc의 시작 주소를 저장하고 있다면, 그 할당 구간을 해제하고 var에 0을 저장한다. var가 이미 0이면 아무 일도 일어나지 않는다.
  3. print(var);
    • var에 저장된 값을 출력한다.

모든 명령은 세미콜론(;)으로 끝난다. 변수 이름은 알파벳 소문자 네 글자이다. 서로 다른 변수는 최대 1,000개이며, 모든 변수의 초깃값은 0이다.

입력

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

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

print 명령은 한 번 이상 주어진다.

출력

print 명령이 실행될 때마다 결과를 한 줄에 하나씩 출력한다.

예제3

  1. 예제 1

    입력
    3
mama=malloc(140);
tata=malloc(120);
print(tata);
    예상 출력
    141

  2. 예제 2

    입력
    5
aabb=malloc(50001);
bbaa=malloc(50000);
print(aabb);
free(aabb);
print(bbaa);
    예상 출력
    1
0

  3. 예제 3

    입력
    5
baka=malloc(214);
baka=malloc(123);
free(baka);
deda=malloc(100);
print(deda);
    예상 출력
    215