번호가 적힌 칸을 한 줄로 이은 기차가 있다. 처음에는 칸이 하나도 없다.
명령은 다섯 가지다.
- front x: 번호가 x인 새 칸을 맨 앞에 붙인다.
- back x: 번호가 x인 새 칸을 맨 뒤에 붙인다.
- cut x: 앞에서부터 보아 처음 만나는 번호 x인 칸 하나를 떼어 낸다. 그런 칸이 없으면 아무것도 하지 않는다.
- rev: 기차 전체의 차례를 거꾸로 뒤집는다.
- show: 지금 칸의 수 k와, 앞에서부터 칸의 번호 k개를 빈칸 하나씩 띄워 한 줄로 출력한다. 칸이 없으면 0만 출력한다.
첫 줄에 명령 수 q, 다음 q줄에 명령이 하나씩 주어진다.
칸마다 번호와 다음 칸을 가리키는 포인터를 가진 연결 리스트로 풀어 보자.
기차는 첫 칸을 가리키는 포인터 head와, 마지막 칸의 next 자리를 가리키는 포인터의 포인터 tailp로 들고 다닌다.
cut은 첫 칸을 따로 다루지 말고, "지금 칸을 가리키는 포인터"의 주소 Node **pp를 옮기며 걷는 함수로 만들어 보자.
입력
1 ≤ q ≤ 10,000, 1 ≤ x ≤ 9,999. show가 출력하는 번호는 모두 합쳐 30,000개 이하다. show는 한 번 이상 나온다.
출력
show마다 한 줄
예시 1 · stdin
9
back 3
front 1
back 7
cut 3
show
rev
back 2
cut 1
show
stdout
2 1 7
2 7 2
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 2개 언어 풀이
이 문제는 C·C++만 받아요. 포인터 변수의 주소를 다시 포인터에 담는 Node **는 두 언어에만 있고, Python·JavaScript·TypeScript·Java·크레이콘은 참조로 다음 칸을 가리킬 수는 있어도 '참조를 담은 자리'의 주소는 쥘 수 없어서, 첫 칸을 뗄 때는 head를 따로 바꾸거나 가짜 첫 칸(dummy)을 둬요. C#은 포인터를 unsafe 안에서만 쓰고, 비슷한 일은 ref 지역 변수(C# 7.3부터 pp = ref pp.Next로 다시 가리키기)로 흉내 내요. C·C++는 for (Node **pp = &t->head; *pp; pp = &(*pp)->next)로 걸으면 *pp가 첫 칸에서는 head 자체, 가운데에서는 앞 칸의 next 자체라서 *pp = gone->next; 한 줄로 어디서든 떼어져요. 맨 뒤에 붙일 자리도 같은 생각으로 Node **tailp(비었으면 &head)에 두면 *tailp = nd; tailp = &nd->next;가 돼요. 기차를 바꾸는 함수는 Train *t처럼 주소로 받아요. C++는 칸을 std::deque<Node>에 담았어요. std::vector는 커질 때 칸을 옮겨서 이미 쥔 Node *가 엉뚱한 곳을 가리키게 돼요. 함정 넷: ① C에서 void cut(Train t, int x)처럼 값으로 받으면 가운데 칸은 잘 떼어지지만(칸들은 포인터로 이어져 있으니까), 첫 칸을 떼어도 진짜 head는 그대로고 마지막 칸을 떼어도 진짜 tailp는 그대로예요. ② 마지막 칸을 떼고 tailp = pp로 고치지 않으면, 다음 back이 이미 떼어 낸 칸 뒤에 붙어서 사라져요. ③ 앞 칸 p에서 p->next를 보며 걷는 흔한 방법은 첫 칸을 한 번도 보지 않아요. 그래서 첫 칸만 따로 다뤄야 하는데, Node **pp는 그럴 필요가 없어요. ④ rev 뒤에 tailp를 옛 첫 칸(이제 마지막 칸)의 next로 옮기지 않으면, 다음 back이 엉뚱한 칸 뒤에 붙어서 칸들이 사라져요.
C++main.cpp · 78 줄
#include <deque>#include <iostream>#include <string>struct Node { int val; Node *next = nullptr;};struct Train { Node *head = nullptr; // 첫 칸(비었으면 nullptr) Node **tailp = &head; // 마지막 칸의 next 자리(비었으면 &head) Train() = default; Train(const Train &) = delete; // tailp가 자기 멤버를 가리키니 복사하면 안 된다 void push_front(Node *nd) { nd->next = head; if (head == nullptr) tailp = &nd->next; head = nd; } void push_back(Node *nd) { *tailp = nd; tailp = &nd->next; } // pp는 "지금 칸을 가리키는 포인터"의 주소: 첫 칸도 가운데 칸도 *pp만 바꾸면 떼어진다 void cut(int x) { for (Node **pp = &head; *pp != nullptr; pp = &(*pp)->next) { if ((*pp)->val == x) { Node *gone = *pp; *pp = gone->next; if (gone->next == nullptr) tailp = pp; return; } } } void reverse() { Node *prev = nullptr, *cur = head; tailp = cur ? &cur->next : &head; while (cur != nullptr) { Node *next = cur->next; cur->next = prev; prev = cur; cur = next; } head = prev; }};int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::deque<Node> pool; // deque는 뒤에 붙여도 있던 칸의 주소가 바뀌지 않는다(vector는 바뀔 수 있다) Train t; int q, x; std::string cmd; std::cin >> q; for (int i = 0; i < q; i++) { std::cin >> cmd; if (cmd == "front" || cmd == "back") { std::cin >> x; Node *nd = &pool.emplace_back(Node{x}); if (cmd == "front") t.push_front(nd); else t.push_back(nd); } else if (cmd == "cut") { std::cin >> x; t.cut(x); } else if (cmd == "rev") { t.reverse(); } else { int k = 0; for (Node *p = t.head; p; p = p->next) k++; std::cout << k; for (Node *p = t.head; p; p = p->next) std::cout << ' ' << p->val; std::cout << '\n'; } }}
Cmain.c · 93 줄
#include <stdio.h>#include <string.h>typedef struct Node { int val; struct Node *next;} Node;typedef struct { Node *head; /* 첫 칸(비었으면 NULL) */ Node **tailp; /* 마지막 칸의 next 자리(비었으면 &head): 여기에 붙이면 맨 뒤 */} Train;static Node pool[10000]; /* 명령마다 칸은 많아야 하나 생긴다 */static int used = 0;Node *new_node(int val) { Node *nd = &pool[used++]; nd->val = val; nd->next = NULL; return nd;}/* 기차를 바꾸는 함수는 모두 Train의 주소를 받는다 */void push_front(Train *t, Node *nd) { nd->next = t->head; if (t->head == NULL) t->tailp = &nd->next; t->head = nd;}void push_back(Train *t, Node *nd) { *t->tailp = nd; t->tailp = &nd->next;}/* pp는 "지금 칸을 가리키는 포인터"의 주소: 첫 칸이든 가운데 칸이든 똑같이 *pp만 바꾸면 떼어진다 */void cut(Train *t, int x) { for (Node **pp = &t->head; *pp != NULL; pp = &(*pp)->next) { if ((*pp)->val == x) { Node *gone = *pp; *pp = gone->next; if (gone->next == NULL) t->tailp = pp; /* 마지막 칸을 뗐으면 붙일 자리가 앞으로 온다 */ return; } }}void reverse(Train *t) { Node *prev = NULL, *cur = t->head; t->tailp = cur ? &cur->next : &t->head; /* 지금 첫 칸이 뒤집은 뒤 마지막 칸 */ while (cur != NULL) { Node *next = cur->next; cur->next = prev; prev = cur; cur = next; } t->head = prev;}void show(const Train *t) { int k = 0; for (const Node *p = t->head; p != NULL; p = p->next) k++; printf("%d", k); for (const Node *p = t->head; p != NULL; p = p->next) printf(" %d", p->val); printf("\n");}int main(void) { int q, x; char cmd[8]; Train t; t.head = NULL; t.tailp = &t.head; scanf("%d", &q); for (int i = 0; i < q; i++) { scanf("%7s", cmd); if (strcmp(cmd, "front") == 0) { scanf("%d", &x); push_front(&t, new_node(x)); } else if (strcmp(cmd, "back") == 0) { scanf("%d", &x); push_back(&t, new_node(x)); } else if (strcmp(cmd, "cut") == 0) { scanf("%d", &x); cut(&t, x); } else if (strcmp(cmd, "rev") == 0) { reverse(&t); } else { show(&t); } } return 0;}