[Coding] 백준 10866,2164 C++

문채영·2023년 3월 25일
0

💻10866

틀렸던 부분:
empty 함수에서
return (n==1);
이라고 해야 한다.
(n=1)이라고 하면 bool이 안먹히는 듯

#include<iostream>
#include<string>
using namespace std;

class Node {
public:
	int data;
	Node* next;

	Node(int e) {
		this->data = e;
		this->next = NULL;
	}
};

class SLinkedList {
public:
	Node* head;
	Node* tail;
	int n;

	SLinkedList() {
		head = NULL;
		tail = NULL;
		n = 0;
	}
	void push_front(int X) {//머리에 노드 추가하기
		if (empty()) {//리스트가 비어 있을 때
			Node* v = new Node(X);//노드 생성
			head = tail = v;//head, tail이 v를 가리키도록
			v->next = NULL;//v의 다음은 null
		}
		else {//리스트에 이미 노드가 있을 때
			Node* v = new Node(X);//노드 생성
			v->next = head;//새 노드의 next가 head노드
			head = v;//head가 새 노드를 가리키게
		}
		n++;
	}

	int pop_front() {//머리노드 삭제하기
		if (empty()) return -1;
		else {
			Node* SNode = head;//임시노드 생성해서 head노드 가리키기
			head = SNode->next;//head가 임시노드(head)의 다음을 가리키게
			int x = SNode->data;
			n--;
			delete SNode;
			return x;
		}
	}
	int pop_back() {//꼬리노드 삭제하기
		if (empty()) return -1;
		else {
			Node* current = head;//current가 head노드를 가리키게
			if (current == tail) {//노드가 하나 뿐이라면
				int temp = tail->data;
				head = tail = NULL;//head,tail이 null을 가리키게
				delete current;//current 삭제
				n--;
				return temp;
			}
			else {//노드가 두 개 이상이라면
				while (current->next != tail)//current의 next가 tail이 아닌동안
					current = current->next;//current를 다음 노드로 이동
				tail = current; //tail 이 current를 가리키게 함
				n--;
				int x = tail->next->data;
				delete tail->next;//tail의 next(원래 맨 마지막노드)를 삭제
				tail->next = NULL;//tail의 next를 null로 수정
				return x;
			}
		}

	}

	int front() {//리스트의 가장 앞 노드의 원소값 반환
		if (empty()) { return -1; }//리스트가 비어 있을 때
		else
		{
			return head->data;
		}
	}
	int back() {//리스트의 가장 앞 노드의 원소값 반환
		if (empty()) { return -1; }//리스트가 비어 있을 때
		else
		{
			return tail->data;
		}
	}

	bool empty() {
		return(n ==0);
	}

	void push_back(int X) {//리스트의 가장 뒤에 노드 삽입
		Node* v = new Node(X);
		if (empty()) {
			head = tail = v;
			v->next = NULL;
		}
		else {
			tail->next = v;
			tail = v;
			v->next = NULL;
		}
		n++;
	}
	int size() {
		return n;
	}
};

int main() {
	int M;
	cin >> M;
	SLinkedList S;
	for (int i = 0; i < M; i++) {
		string k;
		cin >> k;
		if (k == "empty")
			cout << S.empty() << endl;
		else if (k == "front")
			cout << S.front() << endl;
		else if (k == "back")
			cout << S.back() << endl;
		else if (k == "pop_front")
			cout << S.pop_front() << endl;
		else if (k == "pop_back")
			cout << S.pop_back() << endl;
		else if (k == "push_front")
		{
			int x;
			cin >> x;
			S.push_front(x);
		}
		else if (k == "size")
			cout << S.size() << endl;
		else if (k == "push_back") {
			int x;
			cin >> x;
			S.push_back(x);
		}
	}
	return 0;
}

💻단일 연결리스트를 이용한 2164번 구현

#include<iostream>
#include<string>
using namespace std;

class Node {
public:
	int data;
	Node* next;

	Node(int e) {
		this->data = e;
		this->next = NULL;
	}
};

class SLinkedList {
public:
	Node* head;
	Node* tail;
	int n;

	SLinkedList() {
		head = NULL;
		tail = NULL;
		n = 0;
	}

	int pop_front() {//머리노드 삭제하기
		if (head == NULL) return -1;
		else {
			Node* SNode = head;//임시노드 생성해서 head노드 가리키기
			head = SNode->next;//head가 임시노드(head)의 다음을 가리키게
			int x = SNode->data;
			n--;
			delete SNode;
			return x;
		}
	}

	void push_back(int X) {//리스트의 가장 뒤에 노드 삽입
		Node* v = new Node(X);
		if (head == NULL) {
			head = tail = v;
			v->next = NULL;
		}
		else {
			tail->next = v;
			tail = v;
			v->next = NULL;
		}
		n++;
	}

	int size() {
		return n;
	}

	int card() {
		while (size()!= 1) {
			pop_front();
			int temp = head->data;//head의 data 임시저장
			pop_front();
			push_back(temp);
			if (size() == 1) break;
		}
		return head->data;
	}
};

int main() {

	int a;
	cin >> a;
	SLinkedList S;
	for (int i = 1; i <= a; i++) {
		S.push_back(i);
	}
	cout << S.card();
}

0개의 댓글