정수를 담는 표가 있다. 표의 줄마다 담긴 값의 수가 다를 수 있고, 값이 하나도 없는 줄도 있다.
처음에는 줄이 하나도 없다. 줄 번호는 1부터 센다.
명령은 여섯 가지다.
- new k v1 … vk: 값 k개가 든 새 줄을 표의 맨 아래에 붙인다. k는 0일 수 있다.
- copy i: i번 줄과 같은 값이 든 새 줄을 표의 맨 아래에 붙인다. 그 뒤 두 줄은 서로 상관없이 따로 바뀐다.
- add i v: i번 줄의 끝에 값 v를 하나 붙인다.
- set i j v: i번 줄의 j번째 값(1부터 센다)을 v로 바꾼다.
- del i: i번 줄을 지운다. 그 아래 줄들은 번호가 하나씩 앞당겨진다.
- print i: i번 줄의 값의 수 k와 값 k개를 빈칸 하나씩 띄워 한 줄로 출력한다. 줄이 비었으면 0만 출력한다.
명령에 나오는 줄 번호와 값의 자리는 언제나 있는 것이다.
첫 줄에 명령 수 q, 다음 q줄에 명령이 하나씩 주어진다.
print마다 한 줄씩 출력하고, 마지막 줄에 남은 줄의 수와 표 전체에 든 값의 수를 빈칸 하나로 띄워 출력하라.
줄마다 필요한 만큼 메모리를 따로 빌려 풀어 보자(C는 malloc·realloc·free, C++는 std::vector<std::vector<int>>).
copy는 값이 든 블록을 새로 빌려 옮겨 담고, del은 그 줄의 블록을 돌려준다.
입력
1 ≤ q ≤ 50,000, -10⁹ ≤ v ≤ 10⁹. new의 k는 모두 합쳐 100,000 이하다. 어느 때든 표의 줄은 5,000개 이하, 표 전체의 값은 500,000개 이하이고, copy로 복사하는 값은 모두 합쳐 500,000개 이하, print가 출력하는 값은 모두 합쳐 30,000개 이하다.
출력
print마다 한 줄, 그리고 마지막 줄에 "줄의수 값의수"
예시 1 · stdin
9
new 3 1 2 3
copy 1
set 2 1 9
add 1 4
new 0
add 3 -5
del 2
print 1
print 2
stdout
4 1 2 3 4
1 -5
2 5
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 2개 언어 풀이
이 문제는 C·C++만 받아요. 줄마다 메모리를 직접 빌리고 돌려주는 일은 두 언어의 몫이고, Python·JavaScript·TypeScript·Java·C#·크레이콘의 목록은 알아서 늘어나고 가비지 컬렉터가 치워 줘요(그 언어들도 copy는 row[:]·[...row]·new ArrayList<>(row)·new List<int>(row)처럼 복사본을 따로 만들어야 해요). C는 줄마다 int *data·길이·용량을 가진 구조체를 두고, 줄을 담는 표도 Row *로 빌려서 두 겹으로 빌려요. 늘릴 때는 realloc이 돌려준 포인터를 확인한 다음 담고, del은 free(data) 뒤에 겹치는 자리를 당기니 memcpy가 아니라 memmove를 써요. 표를 realloc하면 블록이 옮겨질 수 있어서, 그 전에 쥔 &t.rows[i] 같은 포인터는 다시 구해요. 마지막에는 줄마다 free한 다음 표를 free해요. C++는 std::vector가 빌리기·늘리기·돌려주기를 모두 맡고(RAII), std::vector<int> dup = rows[i];처럼 복사하면 새 블록에 값을 모두 옮겨 담아요. 함정 넷: ① C에서 t.rows[n] = t.rows[i];처럼 구조체를 대입하면 data 포인터만 복사되어 두 줄이 한 블록을 함께 써요. 한쪽을 set하면 다른 쪽도 바뀌고, 끝에 같은 블록을 두 번 free해서 멈춰요. ② memcpy(dst, src, len)의 셋째 인자는 칸 수가 아니라 바이트 수예요. len * sizeof(int)라야 하고, len만 넘기면 앞의 4분의 1만 복사돼요. ③ C++에서 auto row = rows[i]; row.push_back(v);는 복사본에 붙여요. 원본을 바꾸려면 auto &row예요. ④ C++에서 row.reserve(k) 뒤에 row[j]에 쓰면, reserve는 용량만 늘리고 크기는 0 그대로라 그 줄은 빈 줄로 남아요. std::vector<int> row(k)나 resize(k)로 칸을 만들어요.
C++main.cpp · 45 줄
#include <iostream>#include <string>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); // 바깥 vector가 줄들을, 안쪽 vector가 줄마다 값들을 빌려 쥔다. 지워지면 알아서 돌려준다(RAII) std::vector<std::vector<int>> rows; int q; std::cin >> q; std::string cmd; while (q--) { std::cin >> cmd; int i, j, k, v; if (cmd == "new") { std::cin >> k; std::vector<int> row(k); // 크기 k: 칸이 k개 생긴다(reserve는 칸을 만들지 않는다) for (int &x : row) std::cin >> x; rows.push_back(std::move(row)); } else if (cmd == "copy") { std::cin >> i; std::vector<int> dup = rows[i - 1]; // vector 복사는 새 블록을 빌려 값을 모두 옮긴다(깊은 복사) rows.push_back(std::move(dup)); } else if (cmd == "add") { std::cin >> i >> v; rows[i - 1].push_back(v); } else if (cmd == "set") { std::cin >> i >> j >> v; rows[i - 1][j - 1] = v; } else if (cmd == "del") { std::cin >> i; rows.erase(rows.begin() + (i - 1)); // 그 줄의 블록을 돌려주고 뒤를 당긴다 } else { std::cin >> i; const auto &row = rows[i - 1]; std::cout << row.size(); for (int x : row) std::cout << ' ' << x; std::cout << '\n'; } } long long cells = 0; for (const auto &row : rows) cells += row.size(); std::cout << rows.size() << ' ' << cells << '\n';}
Cmain.c · 98 줄
#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct { int *data; /* 이 줄의 값들을 담으려고 빌린 블록 */ int len; /* 들어 있는 값의 수 */ int cap; /* 빌린 칸의 수 */} Row;typedef struct { Row *rows; int n, cap;} Table;/* 빌리기에 실패하면 멈춘다(받은 포인터를 확인한 다음에 담는다) */static void *grow(void *p, size_t count, size_t size) { void *q = realloc(p, count * size); if (q == NULL) { fprintf(stderr, "out of memory\n"); exit(1); } return q;}/* 표 끝에 빈 줄 자리를 하나 만들어 그 주소를 돌려준다. 표의 블록이 옮겨질 수 있으니, 이 함수를 부르기 전에 쥔 Row 포인터는 부른 뒤에 쓰지 않는다 */static Row *append_row(Table *t, int cap) { if (t->n == t->cap) { t->cap = t->cap ? t->cap * 2 : 4; t->rows = grow(t->rows, (size_t)t->cap, sizeof *t->rows); } Row *r = &t->rows[t->n++]; r->len = 0; r->cap = cap > 0 ? cap : 1; r->data = malloc((size_t)r->cap * sizeof *r->data); if (r->data == NULL) exit(1); return r;}static void push(Row *r, int v) { if (r->len == r->cap) { r->cap *= 2; r->data = grow(r->data, (size_t)r->cap, sizeof *r->data); } r->data[r->len++] = v;}int main(void) { Table t = {NULL, 0, 0}; int q, i, j, k, v; char cmd[8]; if (scanf("%d", &q) != 1) return 0; while (q--) { scanf("%7s", cmd); if (strcmp(cmd, "new") == 0) { scanf("%d", &k); Row *r = append_row(&t, k); for (j = 0; j < k; j++) { scanf("%d", &v); push(r, v); } } else if (strcmp(cmd, "copy") == 0) { scanf("%d", &i); int len = t.rows[i - 1].len; Row *dst = append_row(&t, len); /* 먼저 자리를 만들고 */ const Row *src = &t.rows[i - 1]; /* 그다음 원본 주소를 쥔다 */ memcpy(dst->data, src->data, (size_t)len * sizeof *src->data); /* 바이트 수 = 칸 수 × 칸 크기 */ dst->len = len; } else if (strcmp(cmd, "add") == 0) { scanf("%d %d", &i, &v); push(&t.rows[i - 1], v); } else if (strcmp(cmd, "set") == 0) { scanf("%d %d %d", &i, &j, &v); t.rows[i - 1].data[j - 1] = v; } else if (strcmp(cmd, "del") == 0) { scanf("%d", &i); free(t.rows[i - 1].data); /* 뒤의 줄들을 한 칸씩 당긴다: 겹치는 자리라 memcpy가 아니라 memmove */ memmove(&t.rows[i - 1], &t.rows[i], (size_t)(t.n - i) * sizeof *t.rows); t.n--; } else { scanf("%d", &i); const Row *r = &t.rows[i - 1]; printf("%d", r->len); for (j = 0; j < r->len; j++) printf(" %d", r->data[j]); printf("\n"); } } long long cells = 0; for (i = 0; i < t.n; i++) { cells += t.rows[i].len; free(t.rows[i].data); /* 줄마다 빌린 블록을 돌려주고 */ } free(t.rows); /* 마지막으로 표의 블록을 돌려준다 */ printf("%d %lld\n", t.n, cells); return 0;}