ProblemSolving/Linked List

SWEA 암호문3, (C++)

OSNIM 2023. 2. 24. 18:09
반응형

 

위 문제는 삽입/삭제가 많아 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++ 메모

  1. Node*& head에서 *&와 그냥 head 차이 
    • Node*& head는 head라는 포인터 변수에 대한 레퍼런스(reference)를 매개변수로 받는 함수입니다. 따라서 head 변수가 가리키는 값(즉, 연결 리스트의 첫 번째 노드)을 변경할 수 있습니다.
    • head만 인자로 받으면 head의 값(즉, 첫 번째 노드의 포인터)을 복사한 새로운 포인터 변수가 함수 내부로 전달되기 때문에, 함수 내부에서 head 변수의 값(즉, 첫 번째 노드의 포인터)을 변경하더라도 실제로는 원본 head 변수의 값이 변경되지 않습니다. 이에 반해, Node*& head로 매개변수를 선언하면, 함수 내부에서 head의 값(즉, 첫 번째 노드의 포인터)을 변경하면 원본 head 변수의 값도 함께 변경됩니다. 이런 이유로 연결 리스트에서는 보통 Node*& 타입으로 매개변수를 선언합니다.
  2. nullptr은 C++11에서 추가된 null pointer 상수이며, C++11 이전에는 NULL 매크로가 사용되었습니다. nullptr와 NULL은 모두 null pointer를 나타내는데, 차이점은 nullptr은 타입 안정성을 보장하기 위해 도입되었다는 점입니다. nullptr는 포인터 타입에만 사용할 수 있으며, NULL은 정수 타입으로 취급되어 혼란을 일으킬 수 있습니다.따라서 C++11 이후의 코드에서는 nullptr를 사용하는 것이 좋습니다.
  3. cur = cur->next; 에서 '->' 는?
    • '->'는 포인터 변수가 가리키는 객체의 멤버에 접근할 때 사용하는 연산자입니다. 포인터 변수에는 객체의 주소가 저장되어 있으므로, 포인터 변수가 가리키는 객체의 멤버에 접근하려면 '->' 연산자를 사용하여 접근합니다.
    • 예를 들어, 다음과 같은 코드에서 ptr은 Node 객체를 가리키는 포인터 변수이고, ptr->val은 ptr이 가리키는 Node 객체의 val 멤버에 접근하는 것입니다.
struct Node {
    int val;
    Node* next;
};

Node* ptr = new Node();
ptr->val = 10;

 

반응형