문제
0 ~ 999999 사이의 수를 나열하여 만든 암호문이 있다.
암호문을 급히 수정해야 할 일이 발생했는데, 이 암호문은 특수 제작된 처리기로만 수정이 가능하다.
이 처리기는 다음과 같이 3개의 기능을 제공한다.
1. I(삽입) x, y, s : 앞에서부터 x의 위치 바로 다음에 y개의 숫자를 삽입한다.
s는 덧붙일 숫자들이다.[ ex) I 3 2 123152 487651 ]
2. D(삭제) x, y : 앞에서부터 x의 위치 바로 다음부터 y개의 숫자를 삭제한다.[ ex) D 4 4 ]
3. A(추가) y, s : 암호문의 맨 뒤에 y개의 숫자를 덧붙인다. s는 덧붙일 숫자들이다. [ ex) A 2 421257 796813 ]
위의 규칙에 맞게 작성된 명령어를 나열하여 만든 문자열이 주어졌을 때, 암호문을 수정하고, 수정된 결과의 처음 10개 숫자를 출력하는 프로그램을 작성하여라.
[입력]
첫 번째 줄 : 원본 암호문의 길이 N ( 2000 ≤ N ≤ 4000 의 정수)
두 번째 줄 : 원본 암호문
세 번째 줄 : 명령어의 개수 ( 250 ≤ M ≤ 500 의 정수)
네 번째 줄 : 명령어
위와 같은 네 줄이 한 개의 테스트 케이스이며, 총 10개의 테스트 케이스가 주어진다.
[출력]
기호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 수정된 암호문의 처음 10개 항을 출력한다.
코드
#include<iostream>
constexpr size_t MAX_NODE = 99999;
using namespace std;
struct node {
int data;
node* next;
};
int cop_node_count = 0;
node node_pool[MAX_NODE];
node* head = nullptr;
node* new_node(int data)
{
node_pool[cop_node_count].data = data;
node_pool[cop_node_count].next = nullptr;
return &node_pool[cop_node_count++];
}
int main(int argc, char** argv)
{
int test_case;
int T=10;
char command;
int n, secret, m,x,y,s;
for (test_case = 1; test_case <= T; ++test_case)
{
head = 0;
cop_node_count = 0;
cin >> n;
node* main_temp = 0;
for (int i = 0; i < n; i++)
{
cin >> secret;
node* _node = new_node(secret);
if (head == 0)
{
head = _node;
main_temp = head;
}
else
{
main_temp->next = _node;
main_temp = main_temp->next;
}
}
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> command;
if (command == 'I')
{
cin >> x >> y;
node* temp = head;
for (int i = 1; i < x; i++)
{
temp = temp->next;
}
for (int i = 0; i < y; i++)
{
cin >> s;
node* insert_new = new_node(s);
if (i == 0 && x == 0)
{
insert_new->next = head;
head = insert_new;
temp = head;
continue;
}
insert_new->next = temp->next;
temp->next = insert_new;
temp = temp->next;
}
}
else if (command == 'D')
{
cin >> x >> y;
node* temp1 = head;
for (int i = 1; i < x; i++)
{
temp1 = temp1->next;
}
for (int i = 0; i < y; i++)
{
if (x == 0)
{
head = head->next;
temp1 = head;
continue;
}
temp1->next = temp1->next->next;
}
}
else if (command == 'A')
{
cin >> y;
node* temp = head;
while (temp->next != 0)
{
temp = temp->next;
}
for (int i = 0; i < y; i++)
{
cin >> s;
node* temp1 = new_node(s);
temp->next = temp1;
temp = temp->next;
}
}
}
cout << "#" << test_case << " ";
for (int i = 0; i < 10; i++)
{
cout << head->data;
head = head->next;
if (i < 9)
{
cout << " ";
}
else if (i == 9)
{
cout<<endl;
}
}
}
return 0;
}
설명
문제를 처음 읽었을 때는 되게 복잡해 보일 수 있지만
차근차근 읽어보면 단순한 Linked List의 문제이다.
각 알파벳(I, D, A)에 해당하는 경우를 나누어주고
그에 알맞게 삽입, 삭제, 추가의 기능을 구현해준다.
후기
기본적인 Linked List 구현을 할 줄 안다면 쉽게 풀 수 있는 문제였다.
