문제
N개의 10억 이하 자연수로 이뤄진 수열이 주어진다. 이 수열은 완성된 것이 아니라 M번의 편집을 거쳐 완성된다고 한다.
완성된 수열에서 인덱스 L의 데이터를 출력하는 프로그램을 작성하시오.
다음은 미완성 수열과 편집의 예이다.
인덱스
0
1
2
3
4
수열
1
2
3
4
5
I 2 7 -> 2번 인덱스 앞에 7을 추가하고, 한 칸 씩 뒤로 이동한다.
인덱스
0
1
2
3
4
5
수열
1
2
7
3
4
5
D 4 -> 4번 인덱스 자리를 지우고, 한 칸 씩 앞으로 이동한다.
인덱스
0
1
2
3
4
수열
1
2
7
3
5
C 3 8 -> 3번 인덱스 자리를 8로 바꾼다.
인덱스
0
1
2
3
4
수열
1
2
7
8
5
만약 편집이 끝난 후 L이 존재하지 않으면 -1을 출력한다.[입력]
첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 첫 줄에 수열의 길이 N, 추가 횟수 M, 출력할 인덱스 번호 L이 주어지고, 다음 줄에 수열이 주어진다.
그 다음 M개의 줄에 걸쳐 추가할 인덱스와 숫자 정보가 주어진다. 5<=N<=1000, 1<=M<=1000, 6<=L<=N+M
각 I, D, C 명령에서 입력 받는 인덱스의 위치가 존재하지 않는 불가능한 경우는 입력으로 들어오지 않는다.
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
코드
#include <iostream>
constexpr size_t MAX_NODE = 99999;
using namespace std;
struct node {
int data;
node* next;
};
node* head = 0;
node* main_temp = 0;
int node_count = 0;
int cop_node_count = 0;
node node_pool[MAX_NODE];
node* node_new(int data)
{
node_pool[node_count].data = data;
node_pool[node_count].next = nullptr;
return &node_pool[node_count++];
}
void add(int data)
{
node* new_node = node_new(data);
cop_node_count = node_count;
if (head == 0)
{
head = new_node;
main_temp = head;
return;
}
else
{
main_temp->next = new_node;
main_temp = new_node;
}
}
void insert(int pos, int data)
{
node* temp = head;
node* new_node = node_new(data);
cop_node_count++;
int a = pos;
if (pos == 0)
{
new_node->next = head;
head = new_node;
return;
}
while (a > 1)
{
temp = temp->next;
a--;
}
new_node->next = temp->next;
temp->next = new_node;
}
void del(int pos)
{
node* temp = head;
int a = pos;
if (pos == 0)
{
head = head->next;
cop_node_count--;
return;
}
while (a > 1)
{
temp = temp->next;
a--;
}
if (temp->next != 0)
{
temp->next = temp->next->next;
}
cop_node_count--;
}
void change(int pos, int data)
{
node* temp = head;
int a = pos;
while (a > 0)
{
temp = temp->next;
a--;
}
temp->data = data;
}
int main()
{
int t, n, m, l, number,pos,data;
char command;
cin >> t;
for (int q = 0; q < t; q++)
{
cin>> n >> m >> l;
for (int i = 0; i < n; i++)
{
cin >> number;
add(number);
}
for (int i = 0; i < m; i++)
{
cin >> command;
if (command == 'I')
{
cin >> pos >> data;
if (pos+1 <= cop_node_count)
{
insert(pos, data);
}
}
else if (command == 'D')
{
cin >> pos;
if (pos+1 <= cop_node_count)
{
del(pos);
}
}
else if (command == 'C')
{
cin >> pos >> data;
if (pos+1 <= cop_node_count)
{
change(pos, data);
}
}
}
node* temp = head;
int a = l;
while (a > 0)
{
if (temp->next != 0)
{
temp = temp->next;
a--;
}
else {
break;
}
}
if (cop_node_count<l+1)
{
cout << "#"<<q+1<<' '<<-1 <<"\n";
}
else
{
cout << "#" << q + 1 << ' ' << temp->data << "\n";
}
head = nullptr;
cop_node_count = 0;
node_count = 0;
main_temp = nullptr;
}
return 0;
}설명
1230번 문제와 유사하게
입력 받은 문자에 따라서 삽입, 추가, 삭제 기능을 하는 함수를 생성하여
그에 따라 역할을 수행하게 구현하면 되는 문제다.
Linked List 문제를 풀 때는 포인터 값이 null인지 확인만 잘 해주면 될 것 같다.
후기
기본적인 Linked List를 구현할 수 있으면 쉽게 풀 수 있는 문제다.
