[C언어/BOJ] BOJ 1158 요세푸스( 원형연결리스트 구현 )

백준 1158번 요세푸스 문제풀이

 

1158번: 요세푸스 문제

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

풀이 접근

크기가 N인 원형이중연결리스트를 구현하고 3칸씩 가면서 제거 해주고 그 제거해주는 노드를 출력하면 됩니다.

 

 

풀이코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

#include <stdio.h> #include <stdlib.h>   struct Node {       struct Node* next;       struct Node* prev;       int data;   }; //구조체정의   void addnode(int data); //이어붙이기 함수 void RemoveSomething(struct Node* head,int num, int key); struct Node* makenode(int data);// 노드생성 함수 struct Node* head = NULL; struct Node* tail = NULL;   int main() {       int num;     int key;     int count = 0;     scanf_s("%d %d", &num, &key);     for (int i = 1; i <= num; i++)     {         addnode(i);     }       head->prev = tail;     tail->next = head;    RemoveSomething(head,num, key); //key값이 그 밖의숫자인경우 특정노드 삭제로 간다     return 0; }   struct Node* makenode(int data)   {     struct Node* new = malloc(sizeof(struct Node));     new->next = NULL;     new->prev = NULL;     new->data = data;     return new; }   void addnode(int data)   {     struct Node* temp = head;     struct Node* newnode = makenode(data);       if (head == NULL) {         head = newnode;         tail = head;     }       else {           temp = tail; //temp는 tail과 prevNew를 이어주는 도구!           temp->next = newnode;           newnode->prev = temp;           tail = newnode;       }   }   void RemoveSomething(struct Node* head,int num ,int key)// count를 이용해 수정해보기 {       struct Node* tmp = head->prev;//꼬리 노드 저장     int c = 0;     int t = 0;     printf("<");     while (c < num) {           t = key;           while (t--) tmp = tmp->next;//꼬리부터 3칸 이동           printf(c++ ? ", %d" : "%d", tmp->data);           //노드 삭제 알고리즘           tmp->next->prev = tmp->prev;           tmp->prev->next = tmp->next;     }     puts(">");   } Colored by Color Scripter

cs