동적 메모리P0158

두 배로 늘어나는 배열

정수를 담는 늘어나는 배열을 직접 만든다. 배열은 원소의 수(크기)와, 메모리를 빌려 둔 칸의 수(용량)를 따로 가진다. 처음에는 크기가 0, 용량이 1이다. 명령은 네 가지다. - push x: 크기가 용량과 같으면 먼저 용량을 2배로 늘린 다음(늘리기 1번), 맨 뒤에 x를 넣는다. - pop: 비어 있으면 empty를 출력한다.
아니면 맨 뒤의 값을 빼서 출력하고, 그 뒤 용량이 2 이상이고 크기×4가 용량 이하이면 용량을 반으로 줄인다(줄이기 1번). - get i: 0부터 센 i번째 값을 출력한다.
i가 크기 이상이면 out of range를 출력한다. - info: 크기와 용량을 빈칸 하나로 띄워 출력한다. 첫 줄에 명령 수 q, 다음 q줄에 명령이 하나씩 주어진다. 명령마다 위의 출력을 한 줄씩 하고, 마지막 줄에 "grow 늘린횟수 shrink 줄인횟수"를 출력하라. info가 출력하는 용량은 언제나 위 규칙으로 정해지는 값이다. C는 realloc으로 빌린 블록의 크기를 바꾸고, C++는 용량을 변수로 직접 세면서 std::vector의 reserve로 그만큼 미리 빌려 보자.

입력: 1 ≤ q ≤ 100,000, -1,000,000,000 ≤ x ≤ 1,000,000,000, 0 ≤ i ≤ 100,000(정수)
출력: push가 아닌 명령마다 한 줄, 마지막 줄에 "grow G shrink S"

예시 1 · stdin

9
push 4
push 8
push 15
info
get 2
pop
pop
info
get 1

stdout

3 4
15
15
8
1 2
out of range
grow 2 shrink 1

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 2개 언어 풀이

이 문제는 C·C++만 받아요.
빌려 둔 칸의 수를 직접 정하고 옮겨 담는 일은 두 언어의 몫이고, Python list·JS 배열·Java ArrayList·C# List<T>·크레이콘 목록은 알아서 늘어나요(OpenJDK의 Java ArrayList는 1.5배, .NET의 C# List<T>는 2배씩 늘리는 식으로 구현마다 비율이 달라요).
C는 realloc(p, newcap * sizeof *p)가 블록을 늘리거나 줄이고, 그 자리에서 못 늘리면 새 자리로 옮겨 담아 새 주소를 돌려줘요.
실패하면 NULL을 돌려주고 옛 블록은 그대로라서, v->data = realloc(v->data, ...)처럼 바로 덮어쓰면 옛 블록을 잃어요.
받은 포인터를 따로 확인한 다음 담아요.
C++ std::vector도 크기 size()와 용량 capacity()를 따로 가지고, reserve(n)으로 미리 넓혀요.
다만 표준은 reserve(n) 뒤 용량이 n 이상이라는 것만 약속하고, push_back이 스스로 늘리는 비율도 표준 라이브러리마다 달라요(libstdc++·libc++는 2배, MSVC는 1.5배).
그래서 C++ 풀이는 이 문제의 용량을 변수 cap에 직접 세고, reserve(cap)으로 적어도 그만큼 빌려 둬요.
두 배씩 늘리면 옮겨 담는 일이 드물어서 push 한 번의 비용이 평균 O(1)이에요.
함정 넷: ① 1칸씩 늘리면 push마다 옮겨 담아 전체가 O(q²)이고, 용량도 이 문제의 답과 달라요.
② 크기가 용량의 반이 될 때 줄이면, 경계에서 push·pop을 오갈 때마다 늘리고 줄이기를 되풀이해요.
1/4까지 기다렸다 반으로 줄여야 줄인 뒤에도 반이 비어 있어요.
③ C++에서 용량을 따로 세지 않고 capacity()를 그대로 믿으면 줄이기에서 틀려요.
reserve는 용량을 줄이지 못해서 지금보다 작은 값을 주면 아무 일도 하지 않아요.
실제로 칸을 돌려주려면 반만큼 reserve한 새 vector에 옮겨 담고 swap해요.
shrink_to_fit()은 크기에 딱 맞추려 하는(꼭 지키지는 않는) 요청이라 반으로 줄이는 게 아니에요.
④ std::vector<int> v(1)은 칸 하나를 빌리는 게 아니라 0이 든 원소 하나를 만들어요.
빈 채로 칸만 빌리려면 v.reserve(1)이에요.

C++main.cpp · 53 줄

#include <iostream>#include <string>#include <vector> int main() {    std::ios::sync_with_stdio(false);    // 용량은 이 문제의 규칙대로 직접 센다.    // capacity()가 돌려주는 값은 표준 라이브러리마다 다를 수 있다(reserve(n) 뒤에는 n 이상이라는 것만 약속된다).    std::size_t cap = 1;    std::vector<int> v;    v.reserve(cap);  // 크기(size)는 0인 채로 적어도 cap칸을 빌려 둔다    int grow = 0, shrink = 0;    int q;    std::cin >> q;    std::string cmd;    for (int i = 0; i < q; i++) {        std::cin >> cmd;        if (cmd == "push") {            int x;            std::cin >> x;            if (v.size() == cap) {  // 가득 찼으면 두 배로: 늘리는 때를 직접 정한다                cap *= 2;                v.reserve(cap);                grow++;            }            v.push_back(x);  // capacity()가 cap 이상이라 여기서는 다시 옮겨 담지 않는다        } else if (cmd == "pop") {            if (v.empty()) {                std::cout << "empty\n";                continue;            }            std::cout << v.back() << '\n';            v.pop_back();  // 크기만 줄고 빌린 칸은 그대로다            if (cap > 1 && v.size() * 4 <= cap) {                cap /= 2;                // reserve는 칸을 줄이지 못한다: 반만큼 빌린 새 vector에 옮겨 담고 맞바꾼다                std::vector<int> smaller;                smaller.reserve(cap);                smaller.assign(v.begin(), v.end());                v.swap(smaller);                shrink++;            }        } else if (cmd == "get") {            std::size_t k;            std::cin >> k;            if (k < v.size()) std::cout << v[k] << '\n';            else std::cout << "out of range\n";        } else {            std::cout << v.size() << ' ' << cap << '\n';        }    }    std::cout << "grow " << grow << " shrink " << shrink << '\n';}

Cmain.c · 68 줄

#include <stdio.h>#include <stdlib.h>#include <string.h> /* 직접 만든 늘어나는 배열: data는 cap칸을 빌려 두고, 앞의 size칸만 쓴다 */typedef struct {    int *data;    int size, cap;    int grow, shrink;} IntVec; /* 칸 수를 newcap으로 바꾼다. realloc은 자리를 옮길 수 있어서 돌려받은 포인터를 쓴다 */static void resize(IntVec *v, int newcap) {    int *p = realloc(v->data, (size_t)newcap * sizeof *p);    if (p == NULL) {             /* 실패하면 옛 블록은 그대로 남아 있다 */        free(v->data);        exit(1);    }    v->data = p;    v->cap = newcap;} static void push(IntVec *v, int x) {    if (v->size == v->cap) {     /* 가득 찼으면 두 배로: 옮겨 담기가 드물어진다 */        resize(v, v->cap * 2);        v->grow++;    }    v->data[v->size++] = x;} /* 빈 배열이면 0, 아니면 *out에 마지막 값을 꺼내고 1 */static int pop(IntVec *v, int *out) {    if (v->size == 0) return 0;    *out = v->data[--v->size];    if (v->cap > 1 && v->size * 4 <= v->cap) {  /* 1/4 이하로 줄면 반으로 */        resize(v, v->cap / 2);        v->shrink++;    }    return 1;} int main(void) {    IntVec v = { NULL, 0, 0, 0, 0 };    resize(&v, 1);               /* 처음에 한 칸 빌려 둔다 */    int q;    scanf("%d", &q);    for (int i = 0; i < q; i++) {        char cmd[8];        int x;        scanf("%7s", cmd);        if (strcmp(cmd, "push") == 0) {            scanf("%d", &x);            push(&v, x);        } else if (strcmp(cmd, "pop") == 0) {            if (pop(&v, &x)) printf("%d\n", x);            else puts("empty");        } else if (strcmp(cmd, "get") == 0) {            scanf("%d", &x);            if (x < v.size) printf("%d\n", v.data[x]);            else puts("out of range");        } else {            printf("%d %d\n", v.size, v.cap);        }    }    printf("grow %d shrink %d\n", v.grow, v.shrink);    free(v.data);                /* 빌린 블록은 마지막에 한 번 돌려준다 */    return 0;}