[BaekJoon] 1158번 조세퍼스 문제

1158번: 조세퍼스 문제

 

2개의 언어(python, c)로 위 문제를 풀었다. python은 그냥 slicing으로 문제를 풀었다.

#!/bin/python3
# poc.py


def play(node, person, rule):
    result = list()
    while person > 0:
        result.append(node[(rule-1)%len(node)])
        node = node[node.index(result[::-1][0])+1:] + node[:node.index(result[::-1][0])]
        person -= 1
    print("<"+", ".join(result)+">")

if __name__ == "__main__":
    person, rule = map(int, input("").split(' '))
    node = list(map(lambda x : str(x), range(1,person+1)))
    play(node, person, rule)

 

 

언어는 Linked List로 구현을 해보았다.

/* poc.c */

#include <stdio.h>
#include <stdlib.h>

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

void createNode(int person, struct Node *head, struct Node *tail){
    struct Node *node = (struct Node*)malloc(sizeof(struct Node) * person);
    struct Node *tmp = head;
    
    for(int i=0; i<person; i++){
        node[i].data = i + 1;
        tmp->link = &node[i];
        tail->link = &node[i];
        tmp = tmp->link;
    }
    tail->link->link = head->link;
}

void play(int person, int rule, struct Node *head, struct Node *tail){
    struct Node *tmp = head->link;
    int *result = malloc(sizeof(int) * person);
    int index = 0;
    int count = person;
    
    while(count > 0){
        for(int j=0; j<rule-1; j++){
            tail->link->link = tmp;
            tail->link = tail->link->link;
            tmp = tmp->link;
            tail->link->link = tmp;
        }
        result[index] = tmp->data;
        tmp = tmp->link;
        count -= 1;
        index += 1;
    }
    
    printf("<");
    for(int i=0; i<person; i++){
        if(i+1 == person){
            printf("%d", result[i]);
            break;
        }
        else
            printf("%d, ",result[i]);
    }
    printf(">\n");
    free(result);
}

int main(){
    int person;
    int rule;
    struct Node *head = malloc(sizeof(struct Node));
    struct Node *tail = malloc(sizeof(struct Node));
    
    scanf("%d %d",&person, &rule);
    createNode(person, head, tail);
    play(person, rule, head, tail);
    
    free(head);
    free(tail);
}