[백준] 1158 요세푸스 문제 c++ 구현

 

목차

 

 

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 구현 방향

이번 문제는 원형 연결리스트를 직접 구현해보고 싶었기 때문에 c++에 제공된 라이브러리를

이용하지 않고 직접 코드를 작성해 보았다.

 

 

 

원형 연결리스트 설명

adt의 구성은 다음과 같다. 

List* ListInit():

리스트의 초기화를 해준다

 

bool LisEmpty():

리스트가 비어있는 지 확인해주어 비었다면 true를 반환해준다.

 

int LFirst(int* data):

첫번째 데이터의 값을 반환해주고 올바르게 반환이 된었다면 true를 리턴한다.

 

void LPushFront(int data):

머리에 값을 추가해준다.

 

void LPushBack(int data):

꼬리에 값을 추가해준다.

 

int LNext(int* data):

다음 값으로 cur을 움직이고 데이터값을 반환해준다. 올바르게 반환이 되었다면 true를 리턴한다.

 

int LRemove():

현재 참조값을 삭제한 뒤 삭제한 데이터를 반환해준다.

 

int LCount() :

현재 노드의 개수를 반환 해준다.

 

void LClear():

모든 저장된 데이터를 삭제한다.

 

 

 

원형 연결리스트 구현 시 주의할 점

head 포인터 변수는 굳이 구현할 필요가 없다 그 이유는 tail의 다음 노드가 머리가 되기 때문이다.

 

삭제를 하기 위해서 back이라는 포인터 변수를 만들어 주었는데 삭제 시에 그 전 값을 참조해야 하기 때문에 만들었다.

 

삭제 시에 예외처리를 잘 해주어야 한다. 

삭제할 노드가 꼬리일 때와 삭제할 노드가 한 개 남았을 때를 모두 잘 처리해주어야 메모리 누수가 생기지 않는다.

 

 

 

 

문제 풀이

원형 연결리스트가 잘 구현이 되었다면 비교적 쉽게 풀 수 있다.

노드를 순회 시키면서 K로 나누어떨어지는 순서일 때 삭제한후 그 값을 반환해주면 된다.

 

 

 

 

코드 구현

#pragma warning(disable: 4996)
#include <iostream> //  전처리 지시자
#include<string>
#include <cassert>


struct Node {
	struct Node* next;
	int data;
};

class Struct {
private:
	struct List {
		/*Node* head;*/ //head가 필요가 없음 tail->next가 가르키는 것은 head
		Node* tail;
		Node* cur;
		Node* back; // 삭제를 위한 용도
		int count;
	};
	List* list;
public:
	Struct() {
		list = ListInit(); //생성자로 초기화           아래부터 코드를 보면 암묵적으로 this생략가능
	}

	List* ListInit() {
		List* newlist = new List;
		//newlist->head = nullptr;
		newlist->count = 0;
		newlist->tail = nullptr;
		newlist->cur = nullptr;
		newlist->back = nullptr;
		return newlist;
	}
	bool LisEmpty() {
		if (this->list->tail == nullptr) {
			return true;
		}
		else
			return false;
	}
	int LFirst(int* data) { //첫 번째 데이터가 data가 가르키는 메모리에 저장된다.  
		if (this->list->tail == nullptr) {
			return 0;
		}
		this->list->cur = this->list->tail->next;
		this->list->back = this->list->tail;
		//if (this->list->head == nullptr) {
		//	return 0;                 //현재노드가 null이면 false반환
		//}
		*data = this->list->cur->data;
		return 1;

	}
	void LPushFront(int data) {
		Node* newNode = new Node;
		newNode->data = data;
		if (this->list->tail == nullptr) {
			this->list->tail = newNode;
			newNode->next = newNode;
			(this->list->count)++;
		}
		else {
			
			newNode->next = this->list->tail->next;
			this->list->tail->next = newNode;
			(this->list->count)++;
		}

	}
	void LPushBack(int data) {

		Node* newNode = new Node;
		newNode->data = data;
		if (this->list->tail == nullptr) {
			this->list->tail = newNode;
			newNode->next = newNode; 
			(this->list->count)++;
		}
		else {
			newNode->next = this->list->tail->next;
			this->list->tail->next = newNode;
			this->list->tail = newNode;  // 뒤로 추가와의 유일한 차이점임 (사실상 기능은 같음 원형연결이라서)
			(this->list->count)++;

		}

	}
	int LNext(int* data) {  //다음 노드로 이동 
	
		if (this->list->tail == nullptr) { //어짜피 원형 순회이기 때문에 tail이 null이 경우를 예외 처리함
			return 0;
		}
		this->list->back = this->list->cur;  // back을 먼저해야함
		this->list->cur = this->list->cur->next;
		*data = this->list->cur->data;
		return 1;
	}
	//현재 참조값을 삭제한 후 삭제 값 반환 
	int LRemove() {  //LFirst LNext 함수의 마지막 반환 데이터를 삭제
	//두가지 예외 처리 필요! 
		Node* del = this->list->cur;  //현재 참조값을 기준으로 삭제
		int delData = del->data;
		if (this->list->tail == del) {  //삭제할 노드가 꼬리일 떄
	
			if (this->list->tail == this->list->back) { //노드가 하나 남았을 떄
				this->list->tail = nullptr;
			}
			else {
				this->list->tail = this->list->back;  //꼬리와 뒤가 가르키는게 같아짐
			}

		}
		this->list->back->next = this->list->cur->next;
		this->list->cur = this->list->back;
		delete del;
		(this->list->count)--;
		return delData;
	}

	int LCount() {  //있는 노드 개수 반환
		return this->list->count;
	}
	~Struct() {
		delete this->list->tail;
		delete this->list;     //클래스의 소멸시 자동 동적할당 해제
	}

	void LClear() {
		int *data = new int;
		
		if (this->list != nullptr) {

			while (this->LFirst(data)) { //계속 첫 값을 불러와 삭제
				this->LRemove();
				
			}
		}
	}

};

int main() {
	using namespace std;
	Struct list;

	int* data = new int;
	int N, K, i;
	scanf("%d %d", &N, &K);
	for ( i = 1; i <= N; i++) {
		list.LPushBack(i);
	}


	i = 1;
	list.LFirst(data);
	cout << "<";
	while (!list.LisEmpty()) {
		if (i % K ==0 && list.LCount() >= 2) {
			cout << list.LRemove()<<", ";
		}
		else if (i % K == 0 && list.LCount() < 2) {
			cout << list.LRemove() << ">";
		}
		i++;
		list.LNext(data);
	}
	

	



}

 

참고

위의 원형 연결리스트는 아래 책을 바탕으로 공부하였다.

 

윤성우의 열혈 자료구조  

오렌지미디어 · 2012년 01월 16일