[백준][C] 1158-요세푸스/연결리스트/이중연결리스트/LinkedList

[1158] : 요세푸스

 

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

1158번: 요세푸스 문제

 

🤢고난과 역경

• 나는 연결 리스트를 복습하기 위해 이 문제를 시도해보았다.
• 처음에는 원형리스트로 구현해보았지만, 너무 코드가 복잡해져 반례가 계속 계속 나타났고... 굉장히 비효율적인 코드 때문에 시간 초과까지 나왔다. 심지어 내 코드는 나도 못 알아볼 정도로 복잡하고 쓰레기였다..!
• 그래서 이중연결리스트로 바꿔보았고 이 문제에서는 시작 지점이 매번 바뀌어야 하니 head와 tail을 전역 변수로 두고 시작 위치를 head에 저장하며 delete 함수를 작성했다.

💻코드 [C언어]

//1158 - 요세푸스/이중연결리스트
#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct DListNode {
	struct DListNode* next;
	struct DListNode* pre;
	element data;
}Node;

Node* head = NULL;
Node* tail = NULL;

void insert(element data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if (head == NULL) { //노드가 하나도 없을 때 
		head = newNode;
		tail = newNode;
		newNode->pre = head;
		newNode->next = tail;
	}
	else {
		tail->next = newNode;
		newNode->pre = tail;
		head->pre = newNode;
		newNode->next = head;
		tail = newNode;
	}
}

int delete_pos(int pos) {
	Node* p = head;
	if (head == NULL) return 0;

	while (--pos) {
		p = p->next;
	}
	head = p->next; //다음 시작지점 저장

	p->pre->next = p->next;
	p->next->pre = p->pre;

	return p->data;
}

int main(void) {
	int n, k;

	scanf_s("%d %d", &n, &k);

	for (int i = 1; i <= n; i++) {
		insert(i);
	}

	printf("<");
	for (int i = 0; i < n - 1; i++) {
		printf("%d, ", delete_pos(k));
	}
	printf("%d", delete_pos(k));
	printf(">");

	return 0;
}

🎁느낀 점 

• 시간초과를 막기 위해 이중 반복문은 절대 쓰면 안 되겠다고 느꼈다...
• 그리고 다른 사람들의 코드도 많이 관찰해보며 어떻게하면 효율적이고 좋은 코드를 짤 수 있는지 노력해야겠다.

•