반응형
위 문제는 삽입/삭제가 많아 linkedlist를 사용해서 문제를 해결했습니다.
Node 구조체
struct Node {
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
이 코드는 Node 구조체를 정의합니다. 이 구조체는 연결 리스트의 노드를 표현합니다. Node 구조체는 두 개의 멤버 변수를 가지고 있습니다. 하나는 int형 데이터를 저장하는 data이고, 다른 하나는 다음 노드를 가리키는 포인터인 next입니다.
그 다음에는 insert, remove, add, printList 함수가 정의됩니다.
Insert 함수
// 1. I(삽입) x, y, s : 앞에서부터 x의 위치 바로 다음에 y개의 숫자를 삽입한다.
// s는 덧붙일 숫자들이다.[ ex) I 3 2 123152 487651 ]
void insert(Node*& head, int pos, int addCnt) {
Node* prev = nullptr;
Node* cur = head;
for (int i = 0; i < pos && cur; i++) { // cir 이 nullptr이 아닐때만 만족
prev = cur;
cur = cur->next;
}
for (int i = 0; i < addCnt; i++) {
int valToAdd;
cin >> valToAdd;
Node* newNode = new Node(valToAdd);
if (prev) prev->next = newNode;
newNode->next = cur;
if (!prev)head = newNode;
prev = newNode;
}
}
insert 함수는 삽입 연산을 수행합니다. 이 함수는 연결 리스트의 head 포인터와 삽입할 위치(pos), 삽입할 숫자 개수(addCnt)를 인자로 받습니다. 이 함수는 주어진 위치 바로 다음에 주어진 개수의 숫자를 삽입합니다.
for 반복문을 사용하여 pos 위치로 이동합니다. 만약, cur이 nullptr이거나 pos보다 크거나 같은 위치에 도달하면 반복문을 종료합니다.
Delete 함수
// 2. D(삭제) x, y : 앞에서부터 x의 위치 바로 다음부터 y개의 숫자를 삭제한다.[ ex) D 4 4 ]
void remove(Node*& head, int pos, int numToRemove) {
Node* prev = nullptr;
Node* cur = head;
for (int i = 0; i < pos && cur; i++) {
prev = cur;
cur = cur->next;
}
for (int i = 0; i < numToRemove && cur; i++) {
Node* temp = cur;
cur = cur->next;
delete temp;
}
if (prev) prev->next = cur;
else head = cur;
}
remove 함수는 삭제 연산을 수행합니다. 이 함수는 연결 리스트의 head 포인터와 삭제할 위치(pos), 삭제할 숫자 개수(numToRemove)를 인자로 받습니다. 이 함수는 주어진 위치 바로 다음부터 주어진 개수의 숫자를 삭제합니다.
Add 함수
// A(추가) y, s : 암호문의 맨 뒤에 y개의 숫자를 덧붙인다. s는 덧붙일 숫자들이다.
// [ ex) A 2 421257 796813 ]
void add(Node* &head, int numToAdd) {
Node* prev = nullptr;
Node* cur = head;
while (cur) {
prev = cur;
cur = cur->next;
}
for (int i = 0; i < numToAdd; i++) {
int valToAdd;
cin >> valToAdd;
Node* newNode = new Node(valToAdd);
if (prev) prev->next = newNode;
else head = newNode;
prev = newNode;
}
}
add 함수는 추가 연산을 수행합니다. 이 함수는 연결 리스트의 head 포인터와 추가할 숫자 개수(numToAdd)를 인자로 받습니다. 이 함수는 주어진 개수의 숫자를 리스트의 맨 끝에 추가합니다.
전체 코드 (정답)
#include <iostream>
#include <sstream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
// 1. I(삽입) x, y, s : 앞에서부터 x의 위치 바로 다음에 y개의 숫자를 삽입한다.
// s는 덧붙일 숫자들이다.[ ex) I 3 2 123152 487651 ]
void insert(Node*& head, int pos, int addCnt) {
Node* prev = nullptr;
Node* cur = head;
for (int i = 0; i < pos && cur; i++) { // cir 이 nullptr이 아닐때만 만족
prev = cur;
cur = cur->next;
}
for (int i = 0; i < addCnt; i++) {
int valToAdd;
cin >> valToAdd;
Node* newNode = new Node(valToAdd);
if (prev) prev->next = newNode;
newNode->next = cur;
if (!prev)head = newNode;
prev = newNode;
}
}
// 2. D(삭제) x, y : 앞에서부터 x의 위치 바로 다음부터 y개의 숫자를 삭제한다.[ ex) D 4 4 ]
void remove(Node*& head, int pos, int numToRemove) {
Node* prev = nullptr;
Node* cur = head;
for (int i = 0; i < pos && cur; i++) {
prev = cur;
cur = cur->next;
}
for (int i = 0; i < numToRemove && cur; i++) {
Node* temp = cur;
cur = cur->next;
delete temp;
}
if (prev) prev->next = cur;
else head = cur;
}
// A(추가) y, s : 암호문의 맨 뒤에 y개의 숫자를 덧붙인다. s는 덧붙일 숫자들이다.
// [ ex) A 2 421257 796813 ]
void add(Node* &head, int numToAdd) {
Node* prev = nullptr;
Node* cur = head;
while (cur) {
prev = cur;
cur = cur->next;
}
for (int i = 0; i < numToAdd; i++) {
int valToAdd;
cin >> valToAdd;
Node* newNode = new Node(valToAdd);
if (prev) prev->next = newNode;
else head = newNode;
prev = newNode;
}
}
void printList(Node* head) {
for (int i = 0; i < 10 && head; i++) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
int main() {
for (int t = 1; t <= 10; t++) {
int n, M;
cin >> n;
Node* head = nullptr;
for (int i = 0; i < n; i++) {
int val;
cin >> val;
Node* newNode = new Node(val);
if (head) {
Node* cur = head;
while (cur->next) {
cur = cur->next;
}
cur->next = newNode;
}
else {
head = newNode;
}
}
cin >> M;
while (M--) {
char cmd;
cin >> cmd;
if (cmd == 'I') {
int pos, numToAdd;
cin >> pos >> numToAdd;
insert(head, pos, numToAdd);
}
else if (cmd == 'D') {
int pos, numToRemove;
cin >> pos >> numToRemove;
remove(head, pos, numToRemove);
}
else if (cmd == 'A') {
int numToAdd;
cin >> numToAdd;
add(head, numToAdd);
}
}
cout << "#" << t << " ";
printList(head);
}
return 0;
}
반응형
C++ 메모
- Node*& head에서 *&와 그냥 head 차이
- Node*& head는 head라는 포인터 변수에 대한 레퍼런스(reference)를 매개변수로 받는 함수입니다. 따라서 head 변수가 가리키는 값(즉, 연결 리스트의 첫 번째 노드)을 변경할 수 있습니다.
- head만 인자로 받으면 head의 값(즉, 첫 번째 노드의 포인터)을 복사한 새로운 포인터 변수가 함수 내부로 전달되기 때문에, 함수 내부에서 head 변수의 값(즉, 첫 번째 노드의 포인터)을 변경하더라도 실제로는 원본 head 변수의 값이 변경되지 않습니다. 이에 반해, Node*& head로 매개변수를 선언하면, 함수 내부에서 head의 값(즉, 첫 번째 노드의 포인터)을 변경하면 원본 head 변수의 값도 함께 변경됩니다. 이런 이유로 연결 리스트에서는 보통 Node*& 타입으로 매개변수를 선언합니다.
- nullptr은 C++11에서 추가된 null pointer 상수이며, C++11 이전에는 NULL 매크로가 사용되었습니다. nullptr와 NULL은 모두 null pointer를 나타내는데, 차이점은 nullptr은 타입 안정성을 보장하기 위해 도입되었다는 점입니다. nullptr는 포인터 타입에만 사용할 수 있으며, NULL은 정수 타입으로 취급되어 혼란을 일으킬 수 있습니다.따라서 C++11 이후의 코드에서는 nullptr를 사용하는 것이 좋습니다.
- cur = cur->next; 에서 '->' 는?
- '->'는 포인터 변수가 가리키는 객체의 멤버에 접근할 때 사용하는 연산자입니다. 포인터 변수에는 객체의 주소가 저장되어 있으므로, 포인터 변수가 가리키는 객체의 멤버에 접근하려면 '->' 연산자를 사용하여 접근합니다.
- 예를 들어, 다음과 같은 코드에서 ptr은 Node 객체를 가리키는 포인터 변수이고, ptr->val은 ptr이 가리키는 Node 객체의 val 멤버에 접근하는 것입니다.
struct Node {
int val;
Node* next;
};
Node* ptr = new Node();
ptr->val = 10;
반응형