[Python]

def Josephus(n,k):
    a = range(1,n+1)
    m = k - 1
    b = 0
    while len(a) > 1:
        b = ((len(a)+b)%k)
        del a[m::k]
        m = k - b - 1
    return a

print Josephus(10,3)

n,k=map(int,raw_input().split())
s = range(1,n+1)
cursor = 0
while len(s)>1:
    cursor = (cursor+k-1)%len(s)
    s.pop(cursor)
print s[0]

def josephus(num, rem):
    lst = []
    remlst = []
    for i in range(1, num + 1):
        lst.append(i)

    cnt = 1
    while len(lst) != 1:
        for i in lst:
            if cnt % rem == 0:
                remlst.append(i)
            cnt += 1

        for j in remlst:
            lst.remove(j)
            remlst = []

    print lst[0]


josephus(10, 3)

python.

def josephus(n, k):
    n = range(1, n+1)
    pos = k
    while True:
        if len(n) == 1:
            return "answer: %s" % n[0]
        p = n[(pos-1) % len(n)]
        print "next: %s" % p
        cur_pos = n.index(p)
        n.remove(p)
        pos = cur_pos + k

print josephus(100, 3)

C#으로 작성했습니다. 재귀함수로 한번 해보았습니다. O(n) time 입니다.

        public int FindJosephus(int n, int k)
        {
            if (n == 1) return 1;
            return (FindJosephus(n - 1, k) + k - 1)%n + 1;
        }

package test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Scanner;

public class Josephus {

    public static void main(String[] agrs){
        //Scanner sc = new Scanner(System.in);

        int n = 10;
        int k = 3;

        java.util.LinkedList<Integer> list = new LinkedList<Integer>();

        for( int i = 0; i < n; i++){
            list.add(i+1);
        }
        int indexCnt = 1;
        while(list.size() > 1){ 
            ListIterator<Integer> it = list.listIterator();
            while(it.hasNext()){
                int x = it.next();
                if( indexCnt % k == 0){
                    it.remove();
                    System.out.println(x);
                }
                indexCnt++;
            }
        }

        System.out.format("%d", list.get(0));

    }
}

파이썬3.5

기본 아이디어는 itertools.cycle()함수를 이용해서 순환하는 무한 제너레이터를 생각했는데,
중간에 리스트 변화가 있더라도 기존의 리스트로 yield하기 때문에 수정해서 리스트 변화를 반영한
cycle함수를 만들었습니다.

def cycle(a):

    g = iter(a)
    while 1:

        r = next(g, None)    # iteration이 끝나면 None을 반환
        if r is None:
            g = iter(a)
            continue

        yield r


def f(N, K):

    step = 1
    a = [n for n in range(1, N+1)]
    for n in cycle(a):

        if len(a) == 1:
            break

        if step%K == 0:
            a.remove(n)
            step = 1

        step += 1

    return a[0]


if __name__ == '__main__':
    N, K = list(map(int, input('initial data:\n').split()))
    print('\nanswer:\n{}'.format(f(N, K)))

JAVA입니다

package josephus;
import java.util.Scanner;
public class Round {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("initial data:");
        int i,k,alive, N=in.nextInt(), K=in.nextInt();
        boolean p[]=new boolean[N];
        for(i=0;i<N;i++) p[i]=true; // initializing.
        for(i=0,k=0,alive=N;alive>1;i++){
            if(i==N) i=0;
            if(p[i]==true) k++;
            if(k==K){
                p[i]=false; alive--; //killing.
                k=0;
            }
        }
        for(i=0;p[i]==false;i++); //finding the alive.
        System.out.println("answer:\n"+(i+1)); //Print the result.

    }
}

JAVA 병사들 제거되는 순서가 문제 예시처럼 프린트되게 짜봤어요 병사수는 세자릿수까지, round는 두자릿수까지만 정확하게 띄어쓰기가 표시되요;;ㅋㅋ

package josephus;
import java.util.Scanner;
public class Round {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("initial data:");
        int i,j,k,round=0,alive,gap,cipher, N=in.nextInt(), K=in.nextInt();
        boolean p[]=new boolean[N];
        for(i=0;i<N;i++) p[i]=true; // initializing.

        System.out.print("\n1st round:");
        for(i=0,k=0,alive=N,gap=0,cipher=1; alive>1; i++){
            if(i==9) cipher=2; if(i==99) cipher=3; //cipher(자릿수) count for the gap. 세자릿수까지 정확하게 표시됨
            if(i==N){ //round change.
                i=0; round++;
                System.out.print("\n"+(round+1)+((round==1)?"nd": ((round==2)?"rd":"th") )+" round:" );
                for(j=0;j<gap;j++)System.out.print(" ");
                cipher=1;
                if(round==9) gap--; //round 두자릿수까지 정확하게 표시됨
            }
            if(p[i]==true){
                k++;
                if(k==K){
                    p[i]=false; alive--; //killing.
                    k=0;
                    System.out.print(" ("+(i+1)+")");
                    gap=gap+cipher+3;
                }
                else{
                    System.out.print(" "+(i+1)); 
                    gap=gap+cipher+1;
                }
            }
        }

        for(i=0;p[i]==false;i++); //finding the alive.
        System.out.println("\n\nanswer:\n"+(i+1)); //Print the result.

    }
}

[Python 2.7.3] 적당한 offset으로 제거할 시작점을 조절해가면서 K만큼 remove하는 방법을 사용했습니다.

print "initial data : "
problemS = raw_input()
tempL = problemS.split(' ')

N = int(tempL[0])
K = int(tempL[1])

soldiers = [i for i in range(1,N+1)]
compares = soldiers[:]

i = -1
removeL = []
soldiersNum = len(soldiers)
while soldiersNum > 1 :
    i += K
    if i >= soldiersNum :
        i = (-1)*(soldiersNum-(i-K))
        soldiers = compares[:]
        soldiersNum  = len(soldiers)
    else :
        compares.remove(soldiers[i])

print "answer : "
print soldiers

MS Visual Studio 2013, C++로 작성했습니다. STL의 list 자료형이 이 문제에서 쓸만한 것 같네요.

#include <iostream>
#include <list>

using namespace std;

int main(void) {
    unsigned int quantity = 10, interval = 3; // quantity = 수량, interval = 제거 간격

    list<unsigned int> subjectList;
    for (unsigned int i = 1; i <= quantity; i++) subjectList.push_back(i);

    list<unsigned int>::iterator itr = subjectList.begin();
    unsigned int increment_counter = 0;
    if (interval == 1) subjectList.erase(subjectList.begin(), --(subjectList.end()));
    else {
        while (subjectList.size() != 1) {                       
            if (increment_counter >= interval) {
                increment_counter = 1;
                itr = subjectList.erase(itr);
            }
            if (itr != subjectList.end()) itr++;        
            if (itr == subjectList.end()) itr = subjectList.begin();
            increment_counter++;
        }
    }

    cout << "Answer = " << *(subjectList.begin()) << endl;
    return 0;
}

리스트 두 개를 이용하여 짰습니다. 예를 들어, 첫번째 for문이 끝나면 list_1은 그대로 [1,2,3,4,5,6,7,8,9,10], list_2는 [1,2,4,5,7,8,10]가 됩니다. 리스트를 두 개 사용한 이유는 list_1에 대해 for문을 도는데 list_1의 원소를 삭제하면 안될 것 같아서입니다. (즉, list_1을 이용한 for문을 돌 때는 list_2의 원소를 삭제, list_2를 이용한 for문을 돌 때는 list_1을 삭제. for문 이후 두 리스트를 동기화) 처음이라 좋은 코드는 아닌 것 같네요. 많은 피드백 부탁드립니다.

N=10
K=3

list_1=[0]*N
list_2=[0]*N
index=1
index2=[]
count=0

for i in range(N):
    list_1[i]=i+1
    list_2[i]=i+1

while 1:
    for i in range(1,len(list_1)+1): 
        if index%K==0:
            print list_2
            del list_2[i-1-count]
            count=count+1
        index=index+1
    if len(list_2)==1:
        print list_2[0]
        break
    list_1=list_2
    count=0

     for i in range(1,len(list_2)+1):
        if index%K==0:
            print list_1
            del list_1[i-1-count]
            count=count+1
        index=index+1
    if len(list_1)==1:
        print list_1[0]
        break
    list_2=list_1
    count=0

def survive(N, S):
    flags = [True for i in range(N)]
    cur = -1
    while any(flags):
        for i in range(S):
            cur += 1
            if cur >= N:
                cur -= N
            while not(flags[cur]):
                cur += 1
                if cur >= N:
                    cur -= N
        flags[cur] = False

    return cur+1


def main():
    print(survive(10, 1))
    print(survive(10, 2))
    print(survive(10, 3))
    print(survive(10, 13))

clojure

(defn remove-nths
  [n start-idx coll]

  (loop [[fst & rst] coll
         idx start-idx
         acc []]

    (if-not fst
      [idx acc]

      (if (= idx (dec n))
        (recur rst 0 acc)
        (recur rst (inc idx) (conj acc fst))))))


(remove-nths 3 0 [:1 :2 :3 :4 :5 :6 :7 :8 :9 :10])
;=> [1 [:1 :2 :4 :5 :7 :8 :10]]

(remove-nths 3 1 [:1 :2 :4 :5 :7 :8 :10])
;=> [2 [:1 :4 :5 :8 :10]]

(remove-nths 3 2 [:1 :4 :5 :8 :10])
;=> [1 [:4 :5 :10]]

(remove-nths 3 1 [:4 :5 :10])
;=> [1 [:4 :10]]

(remove-nths 3 1 [:4 :10])
;=> [0 [:4]]


(defn problem-josephus
  [n k]
  (loop [[start-idx [fst & rst :as soldiers]] [0 (range 1 (inc n))]]
    (if-not rst
      fst
      (recur (remove-nths k start-idx soldiers)))))


(problem-josephus 10 3)
;=> 4

큐(Queue)를 이용해서 순환시키는 방법으로 다시 만들어 봤습니다.
훨씬 쾌적한 알고리즘이 되었네요.

from collections import deque

class Queue:
    def __init__(self, initValue=[]):
        self.q = deque(initValue)

    def isEmpty(self):
        return len(self.q) == 0

    def enqueue(self, item):
        self.q.append(item)

    def dequeue(self):
        return self.q.popleft()

    def size(self):
        return len(self.q)


def joseph(m, n):
    q = Queue(range(1,m+1))
    while q.size() > 1:
        for i in range(n-1):
            q.enqueue(q.dequeue())
        q.dequeue()
    return q.dequeue()

print joseph(10, 3)

파이썬 3.4 입니다.

머리싸매고 풀어보고 올리기는 하는데, 다른 분들 짜신 걸 보니 놀랍네요...

initial = input().split(" ")
total_list = list(range(1,int(initial[0])+1))
n_th = int(initial[1])

while len(total_list) >= n_th:
    result_list = []
    for x in range(len(total_list)//n_th):
        total_list.pop(n_th-1)
        temp_list = total_list[0:n_th-1]
        total_list[0:n_th-1] = []
        result_list = result_list + temp_list
    result_list = total_list + result_list
    total_list = result_list

while len(total_list) > 1:
    rem = n_th % len(total_list)
    if rem == 0:
        total_list=total_list[:-1]
    else:
        total_list=total_list[rem:]+total_list[:rem-1]

print(total_list[0])

Perl
시키는 대로 합니다.

use strict;
my ($n,$k)=@ARGV;
my @a;
push @a,$_ for (1..$n);
while($a[1]){
    push @a,shift @a for (1..$k-1);
    shift @a
}
print $a[0]

#include<stdio.h>
#include<queue>


void createPerson(std::queue<int> *q, int size);
void kill(std::queue<int> *q ,int k);
void printQueue(std::queue<int> *q);


int main()
{
    std::queue<int> qu;

    createPerson(&qu, 10);

    kill(&qu,3);
    printQueue(&qu);
    return 0;
}

void createPerson(std::queue<int> *q, int size)
{
    for(int i = 0; i < size;i++)
        q->push(i+1);
}

void kill(std::queue<int> *q ,int k)
{
    while(q->size() > 1)
    {
        for(int i = 1; i <= k-1 ;i++)
        {
            q->push(q->front());
            q->pop();
        }
        q->pop();
    }
}
void printQueue(std::queue<int> *q)
{
    while(q->empty() ==false)
    {
        printf("%d ",q->front());
        q->pop();
    }
    printf("\n");
}

import java.util.*;

public class Test { public static void main(String[] args) {

    boolean[] p = new boolean[10];
    int killCount = 3;

    for(int i=0; i < p.length; i++){ p[i] = true; }

    int cut = p.length;
    int count = 0; //3번씩 돌았나 체크
    int pivot = 0; //false 자리 위치

    while(true){

        if(cut == 1) break;
        if(count == p.length) count = 0;
        if(p[count] == true) ++pivot;

        if(pivot == killCount){
            p[count] = false;
            pivot = 0;
            --cut;
        } 
        ++count;
    }
    System.out.println(Arrays.toString(p));
}

}

coding by python beginner

n = 10; k = 3; remain = 0
soldiers = [x for x in range(1, n+1)]

while len(soldiers) > 1:
    for i in range(k-(1+remain), len(soldiers), k):
        soldiers = soldiers[:i] + [False] + soldiers[i+1:]
        remain = len(soldiers[i+1:])    
    soldiers = [x for x in soldiers if x is not False]

print(soldiers[0])

public class Josephus {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int k = Integer.parseInt(sc.nextLine());
        int remained = n;
        sc.close();

        List<Integer> list = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            list.add(i + 1);
        }

        int position = (k - 1) % remained;
        while(remained > 1) {
            list.remove(position);
            remained--;
            position = (position + (k - 1)) % remained;
        }
        System.out.println(list.get(0));
    }
}

    static void exce60()
    {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(),k = scan.nextInt();
        int[] arr = new int[n];
        int cnt = 0,indx = -1;

        while(n-1>cnt)
        {
            for(int i=0;i<k;i++)
            {
                indx = (indx+1)%n;
                if(arr[indx] == 1)
                    i--;
            }

            arr[indx] = 1;
            cnt++;          

        }

        for(int i=0;i<n;i++)
        {
            if(arr[i] == 0)
            {
                System.out.println(i+1);
                break;
            }
        }

    }

print("Please insert the number of soldiers(N) and the distance(L).\nSpace is for the division of each variable.\n")

setting = input()
splitter = (" ")
(solnum, soldis) = setting.split(splitter)
palette = []

try:
    solnum = int(solnum); soldis = int(soldis)
    for i in range(0, solnum):
        palette.append(i+1)

except IOError as ioerr:
    print("\nInvalid Input!\n")
    quit()

print("Basic List: \n")
print(palette)
a = 2
for ii in range(0, len(palette)):
    print("\nRound No. " + str(ii+1)+"\n")
    iii = 0
    while(iii < solnum):
        if (a + soldis*iii) >= len(palette):
            a = (a + soldis*iii) - len(palette)
            iii = 0
            for rmv in palette:
                if type(rmv) is str:
                    palette.remove(rmv)
            break
        elif (a + soldis*iii) < len(palette):
            palette[a + soldis*iii] = str(palette[a + soldis*iii])
            iii = iii + 1
    print(palette)
    if len(palette) == 1:
        answer = str(palette.pop(0))
        print("\n\n" + answer + " is the final survivor!")
        break

매 시행마다 리스트 내의 특정 숫자(죽을 사람)의 자료형을 str로 바꾸고, 시행 후 자료형이 str인 원소를 리스트에서 제거하는 방식으로 구성하였습니다. 그리고 리스트 내에 남은 원소가 1개일 때 그를 최종 생존자로 선언하도록 하였습니다.

파이썬 2.7


def josephus(n,k):
    l = range(1, n+1)  #최초에 1~10까지 저장

    count = 1  #
    l_after = []  # l에 저장된 것 중에 ㅣ % 3인 것을 제외하고 저장함.

    while True:
        for i in range(len(l)):
            if count % k != 0:
                l_after.append(l[i])
            count += 1  # 루프돌 때 카운트,

        print l_after

        if len(l_after) == 1:
            return l_after[0]

        l = l_after[:]  # 하나의 루프가 끝나면
        l_after = []

print josephus(10,3)

결과:
[1, 2, 4, 5, 7, 8, 10]
[1, 4, 5, 8, 10]
[4, 5, 10]
[4, 10]
[4]
4

Ruby

풀이 1

# https://www.quora.com/What-is-the-best-solution-for-Josephus-problem-algorithm
safe_pos = ->n,k { (2..n).reduce(0) {|a,e| (k+a) % e} + 1 } 

풀이 2

safe_pos = ->n,k,ring=[*1..n] {ring.rotate!(k-1).shift until !ring[1]; ring[0]}

Test

expect( safe_pos[10,3] ).to eq 4
expect( safe_pos[100,3] ).to eq 9
expect( Benchmark.realtime { safe[10000000,3] }).to be_within(0.5).of(1)

인원수만큼 1로 채운 리스트를 만들고 3번째 1을 만날 때마다 죽여서 0으로 만듭니다.

def do(n, k):
    s = [1] * n
    i, j = 0, 1
    while sum(s) > 1:
        if j % k == 0:
            s[i] = 0
        i = (i + 1) % n
        j = j + (1 if s[i] == 1 else 0)
    print(s.index(1) + 1)

do(10, 3)

Python 3.4.4

def Josephus(n, k):
    data = list(range(1, n + 1))
    index = k - 1
    temp = 0

    while len(data) > 1:
        temp = (len(data) + temp) % k
        del data[index::k]
        index = k - temp - 1
    return data

n, k = map(int, input().split())
print(Josephus(n, k))

C++ deque를 이용해서 제거되는 순서를 전부 출력해봤어요.

#include <iostream> 
#include <cstdlib>
#include <algorithm> 
#include <deque> 
using namespace std; 

int main()
{
    deque<int> dq;  
    int n,m; 
    cin >> n >> m;   
    for (int i = 1; i <= n; ++i)
    {
        dq.push_back(i);  
    }
    int cnt = 0; 
    cout << "<";
    while (!dq.empty())
    {
        if (cnt == m-1)
        {
            if (dq.size() > 1) cout << dq[0] << ", "; 
            else cout << dq[0] << ">" << endl;
            dq.pop_front(); 
            cnt = 0; 
        }
        else
        {
            dq.push_back(dq[0]);  
            dq.pop_front();   
            ++cnt;  
        }
    }
    return 0; 
}

class pointer:
    def __init__(self, l, startpoint = 0):
        self.l, self.cursor = l, startpoint
    def nxt(self, n):
        self.cursor += n
        self.refresh()
    def delete(self):
        self.l.pop(self.cursor)
        self.refresh()
    def refresh(self):
        self.cursor = self.cursor%len(self.l)
while __name__ == '__main__':
    N, K = list(map(int, input('>>>').split()))
    p = pointer(list(x for x in range(1, N+1)))
    while 1:
        p.nxt(K-1)
        p.delete()
        if len(p.l) == 1:
            break
    print(p.l)

파이썬 3.5.1

java 기존 비슷하지만 array 에 저장한뒤 삭제합니다.

private static void Test42() {
        Scanner in = new Scanner(System.in);
        System.out.println("initial data:");

        int Max = in.nextInt();
        int Gap = in.nextInt();
        in.close();

        int pivot = 0;
        ArrayList<Integer> ar = new ArrayList<Integer>();
        for (int i = 1; i <= Max; i++) {
            ar.add(i);
        }

        int size = ar.size();
        while (ar.size() > 1) {
            pivot += Gap - 1;
            if (pivot > size - 1) {
                pivot = pivot % size;
            }
            System.out.println("kill = " + ar.remove(pivot));
            size--;
        }
        System.out.println(ar);

    }

import java.util.ArrayList;
import java.util.Scanner;

public class test {

    public static void main(String[] argv) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        ArrayList<Integer> numList = new ArrayList<Integer>();

        for(int i = 1; i <= n; i++){
            numList.add(i);
        }

        System.out.println(dieNumber(k, numList));
    }

    public static int dieNumber(int k, ArrayList<Integer> numList){

        for(int i =0; i<numList.size(); i++){
            if(k == 1){
                numList.set(i , 0);
                k = 3;
            }else{
                k--;
            }
        }

        for(int i =0; i<numList.size(); i++) {
            if(numList.get(i) == 0) numList.remove(i);
        }

        if(numList.size() != 1){
            dieNumber(k, numList);
        }

        return numList.get(0);
    }
}

N=int(input('number of soldiers : '))
k=int(input('input k : '))

sol=list(range(1, N+1))

def mod(a): return a%len(sol)

d=k-1
while sol.count(0)<len(sol)-1:
    sol[d]=0; print(sol)
    count=0
    while count<3:
        if sol[mod(d+1)]==0: d=mod(d+1)
        else: count+=1; d=mod(d+1)

Java

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.function.BiFunction;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class JosephusTester {
    public static BiFunction<Integer, Integer, Integer> josephus = (n, k) -> {
        List<Integer> list = new LinkedList<>(IntStream.rangeClosed(1, n).boxed().collect(Collectors.toList()));
        int pos = 0, step = k - 1;
        while (list.size() > 1) {
            pos += step;
            if (pos >= list.size()) {
                pos -= list.size();
            }
            list.remove(pos);
        }
        return list.get(0);
    };

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int size = sc.nextInt();
            int step = sc.nextInt();
            System.out.println(josephus.apply(size, step));
       }
    }
}

• 10 3
• 4

#!/usr/bin/python3

#n, k = map(int,input().split(' '))

n, k = 10, 3
lst = [x+1 for x in range(n)]
ptr = 0
cnt = 1

while len(lst) != 1:
    if cnt % k == 0:
        del lst[ptr]
        cnt = 0
        ptr -= 1
    cnt += 1
    ptr += 1

    if ptr == len(lst):
        ptr = 0

print(lst[0])

더 공부해야겠네요..

def do(n, k):
    list_ = list(range(1, n + 1))
    mod_ = 0
    while len(list_) != 1:
        len_ = len(list_)
        del list_[k - 1 - mod_::k]
        mod_ = (len_ + mod_) % k
    print(list_[0])

do(10, 3)

Python 3.5.2에서 작성하였습니다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication23
{
    class Program
    {
        static void Main(string[] args)
        {
            string input;
            string[] splitInput;
            Console.WriteLine("initial data: ");
            input = Console.ReadLine();
            splitInput = input.Split(' ');

            int armyCount = Convert.ToInt32(splitInput[0]);
            int dieTurn = Convert.ToInt32(splitInput[1]);

            Console.WriteLine(JosephusProblem(armyCount, dieTurn));

        }

        public static int JosephusProblem(int _armyCount, int _dieTurn)
        {
            int armyCount = _armyCount;
            int dieTurn = _dieTurn;

            int count = 0;
            List<int> armyList = new List<int>();

            //병사 세팅
            for (int i = 1; i <= armyCount; i++)
            {
                armyList.Add(i);
            }

            while (armyList.Count > 1) //병사가 한명 남을때까지
            {
                //죽일 병사 찾기
                for (int i = 0; i < armyList.Count; i++)
                {
                    count++;
                    if (count == dieTurn)
                    {
                        armyList[i] = 0; //죽일 병사 0으로 값 대체
                        count = 0;
                    }
                }

                //죽일 병사 죽이기
                for (int i = armyList.Count - 1; i >= 0; i--)
                {
                    if (armyList[i] == 0)
                    {
                        armyList.RemoveAt(i); //병사 죽이기
                    }
                }
            }
            return armyList[0];
        }
    }
}

N,K = list(map(int,input().split(' ')))
_list, count = [x for x in range(1,N+1)], 1

while len(_list) > 1:
    rm_list = list()
    for x in range(len(_list)):
        if count % K == 0:
            rm_list.append(_list[x])
        count += 1
    for x in rm_list:
        _list.remove(x)
print(_list[0])

#### 2017.01.28 D-389 ####

N,K = list(map(int,input().split(' ')))
_list, step = [x for x in range(1,N+1)], 0

while len(_list) > 1:
    step = (step+K-1) % len(_list)
    _list.pop(step)
print(_list[0])

위에껀 제가짠거 아래는 상파님 코드한줄 빌렸습니다.. 한줄 제대로된 코드는 어마어마하게 차이가 나는군요...

#include <stdio.h>
#include <stdlib.h>
int N = 10;
bool verdict(int* arr);
void main() {
    int K = 3;
    int* flag = (int*) malloc (sizeof(int) * N);
    for(int i=0;i<N;i++) 
        flag[i] = true;

    int i = 0;
    int c = 0;
    while(verdict(flag)) {
        if(flag[i] != false)
            c++;
        if(c==K) {
            c=0;
            flag[i] = false;
        }
        i++;
        if(i==N)
            i=0;
    }

    for(int i=0;i<N;i++) {
        if(flag[i]==true)
            printf("%d\n", i+1);
    }
}
bool verdict(int* arr) {
    int c=0;
    for(int i=0;i<N;i++)
        if(arr[i]==true)
            c++;
    if(c==1)
        return false;
    else
        return true;
}

```{.java}

import java.util.LinkedList; import java.util.Scanner;

public class Josephus_Problem {

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    System.out.println("initial data:");
    int N = scan.nextInt();
    int K = scan.nextInt();

    LinkedList<Integer> list = new LinkedList<Integer>();
    for(int i = 0; i < N; i++)
        list.add(i+1);

    for(int i = 1, last = -1, temp = 0; i < N; i++){
        temp = (K + last)%list.size();
        list.remove(temp);
        last = (temp+list.size()-1)%list.size();//temp가 0이되서 last가 -1이 되지않도록 방지

    }

    System.out.println("answer:");
    System.out.println(list.get(0));
    scan.close();
}

}

```> 배열에 N만큼 대입하고 죽는 사람을 지정합니다. 다음 죽는 사람을 지정하는 때는 전에 죽은 사람의 위치 last에서 -1칸 이동하고 K 간격만큼 이동한 곳의 사람을 지정하면 됩니다. temp는 list.remove가 너무 길어지는거 같아서 썼습니다.

import java.util.Arrays;
import java.util.Scanner;

import static java.lang.System.in;

public class JosephusProblem {

    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int f = 0;

        int[] q = new int[n];
        for (int i = 1; i <= n; i++) q[i - 1] = i;

        int[] q1 = Arrays.copyOf(q, q.length);


        while (true) {

            int l = q1.length;
            int[] q2 = new int[l];
            int m = f;
            for (int i = 1; i <= l; i++) {
                m = (i + f) % k;
                if (m != 0) {
                    q2[(i - 1) % l] = q1[i - 1];
                }
            }

            f = m;

            int p = 0;
            for (int i = 0; i < l; i++) {
                if (q2[i] != 0) p++;
            }

            q1 = new int[p];
            int r = 0;
            for (int i = 0; i < l; i++) {
                if (q2[i] != 0) {
                    q1[r] = q2[i];
                    r++;
                }
            }

            if (r == 1) {
                System.out.println(q1[0]);
                break;
            }
        }
    }
}

최초 배열을 생성 N번째 병사를 제외하고 남은 배열을 복사 하고 다시 N번째 병사를 검증을 한다. 병사가 한명 일 때 까지 검증 반복한다.

// 최후의 병사 - C#
using System;
namespace Thefinalsoldier
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("남은 병사 수:");
            int soldiers = int.Parse(Console.ReadLine());
            Console.Write("죽이는 간격:");
            int turn = int.Parse(Console.ReadLine());
            bool[] status = new bool[soldiers];
            int survivor = soldiers; int counter = 0;
            while (true)
            {
                for (int i = 0; i < soldiers; i++)
                {
                    if (status[i] == true)
                        continue;
                    else
                        counter++;
                    if (counter == turn)
                    {
                        counter = 0;
                        status[i] = true;
                        survivor--;
                        Console.Write("({0}) ", i + 1);
                    }
                    else
                        Console.Write("{0} ", i + 1);
                }
                Console.WriteLine();
                if (survivor == 1)
                    break;
            }
            for (int i = 0; i < soldiers; i++)
                if (status[i] == false)
                    Console.WriteLine("마지막 병사: {0}", i + 1);
        }
    }
}

javascript

var input = "10 3";

var safe = function (input) {
    var [n, k] = input.split(" ").map($ => parseInt($));
    var soldiers = Array.from(Array(n), (_, i) => i + 1);
    var index = -1;
    while (soldiers.length > 1) {
        index = (index + k) % soldiers.length;
        soldiers.splice(index, 1);
    }
    return soldiers[0];    
};

console.log(safe(input));

Python: 리스트 사용. 죽은 사람을 따로 카운팅하지 않고 K-1번씩 진행합니다.

def lastone(N, K):
    soldiers = list(range(1, N+1));

    p = 0;
    for lives in range(N, 1, -1):
        p = (p + K - 1) % lives
        soldiers.pop(p)

    return soldiers[0]

print(lastone(10, 3))

.

C#: 배열 구현입니다. 죽은 병사는 -1로 표시

using static System.Console;

class Circle
{
    private int[] arr;
    private int pos;

    public Circle(int N)
    {
        arr = new int[N];
        for (int i = 0; i < N; i++)
        {
            arr[i] = i + 1;
        }
        pos = -1;
    }

    public int moveNext()
    {
        for (int i = 0; i < arr.Length; i++)  // 무한루프 방지
        {
            pos = (pos + 1) % arr.Length;
            if (arr[pos] > 0)
            {
                return arr[pos];
            }
        }
        return -1;  // 모두 사망
    }

    public int kill()
    {
        int t = arr[pos];
        arr[pos] = -1;
        return t;
    }
}
class Josephus
{
    static void Main(string[] args)
    {
        int N = 10, K = 3;
        Circle circle = new Circle(N);

        for (int lives = N; lives > 1; lives--)
        {
            for (int i = 0; i < K; i++)
            {
                circle.moveNext();
            }
            circle.kill();
        }
        WriteLine(circle.moveNext());
    }
}

def josephus(n, k) :

    soldiers = list(range(1, n+1))
    s = 1

    while True :
        if len(soldiers) == 2 :
            break

        elif s == k :
            del soldiers[0]
            s = 1
            continue

        else :
            soldiers.append(soldiers[0])
            del soldiers[0]
            s += 1
            continue

    return soldiers[1]

def f(N, K):
    cnt = 0
    arr1 = list(range(1, N + 1))
    while len(arr1) > 1:
        for i1 in range(0, len(arr1)):
            cnt += 1
            if cnt % K == 0:
                arr1[i1] = 'x'
        arr1 = [x for x in arr1 if x != 'x']
    print(arr1[0])

f(10, 3)

(n, k) = list(map(int, input('input number : ').split()))

soldier = [i for i in range(1, n+1)]
i = 0
while len(soldier) > 1:
    i = (i + k-1) % len(soldier)
    soldier.pop(i)

print(soldier[0])

def josephus(n, k):
    n = range(1, n+1)
    pos = k
    while True:
        if len(n) == 1:
            return "answer: %s" % n[0]
        p = n[(pos-1) % len(n)]
        print "next: %s" % p
        cur_pos = n.index(p)
        n.remove(p)
        pos = cur_pos + k

print josephus(100, 3)

def cycle(n,k):
    nl=[i for i in range(1, n+1)]
    s=0
    def inner(nlist, sun):
        tmp=[nlist[i*k-sun-1] for i in range(1, len(nlist)//k+3) if i*k-sun<=len(nlist)]
        tmpl=[i for i in nlist if i not in tmp]
        print(tmp, tmpl)
        if len(tmpl)==1:
            return(tmpl[0])
        if tmp:
            s=len(nlist)-1-nlist.index(tmp[-1])
        else: s=len(tmpl)
        return(inner(tmpl, s))
    return(inner(nl, s))

print(cycle(10, 3))

print("사람수와 간격을 차례로 입력하시오.")
n,k,num = int(input()), int(input()),0
lst = list(x for x in range(1,n+1))
while len(lst)>1:
    num = (num +k-1)%len(lst)
    print(num,lst, lst.pop(num))
print(lst[0])

파이썬 3.6

• 아이디어>
• 주어진 범위내의 숫자 리스트에서 K 배수의 순서의 숫자를 제거한 리스트를 만들고,
• 원래 숫자 리스트에 연결해서 3의 배수 순서의 숫자를 찾아 제거하는 과정을 한 개의 숫자만 남을 때까지 반복합니다.

def safeposition(N,K):
    print(" initial data:""\n"" %d %d"%(N,K),"\n")
    N_list = list(range(1,N+1))
    new_N = list(range(1,N+1))
    count = K-1
    while count < len(N_list):
        new_N.remove(N_list[count])
        count += K
        if count >= len(N_list):
            N_list.extend(new_N)
    print(" answer:""\n",new_N[0])

if __name__ == "__main__":
    N,K = int(input(" N = ")), int(input(" K = "))
    print("\n")
    safeposition(N,K)

*결과값

 N = 10
 K = 3


 initial data:
 10 3 

 answer:
 4

# 파이썬

input_sample = (10, 3)


def josephus_problem(t1):
    i1, i2 = t1[0], t1[1]
    alive = []
    for m in range(i1):
        alive.append(m+1)
    i = 0
    removed = 0
    while alive:
        i += 1
        if removed == i1 -1:
            return alive[-1]
        elif i % i2 != 0:
            alive.append(alive[i-removed-1])
        else:
            last_removed = alive.pop(i-removed-1)
            removed += 1


print(josephus_problem_step(input_sample))

def josephus(a, b):
    if a == 1:
        return 1
    else:
        result = josephus(a-1, b) + b -1
        return result%a + 1


n = list(map(int, input().split(' ')))
print(josephus(n[0], n[1]))

N=int(input("병사수를 입력하세요:"))
K=int(input("간격을 입력하세요:"))

num_list=[]
for k in range(1,N+1):
    num_list.append(k)

flag=1
index=-1
counter=0
for_delete_list=[]
while flag:
    index+=K
    if index<=N-1:
        for_delete_list.append(num_list[index])
    if index>N-1:
        for num in for_delete_list:
            num_list.remove(num)
        if len(num_list) == 1:
            print(num_list.pop())
            flag = 0
            continue
        for_delete_list=[]
        index=index-N
        N = N - counter
        if index>N-1:
            index=index%N
        for_delete_list.append(num_list[index])
        counter=1
        continue
    counter+=1

파이썬 3.6.4

로직을 짜긴했는데, 뭔가 이렇게까지 길어질 필요가 있을까 하는 느낌이 듭니다..! 좀 더 고민해서 알찬 로직을 다시 구성해봐야 할 듯 합니다.

def jose(N, K) :
    Soldiers = [n for n in range(1,N+1)]
    count = 0
    while len(set(Soldiers)) != 1 :
        a = divmod(len(Soldiers), K)
        for i in range(1,a[0]+1) :
            del Soldiers[(K-1)*i]
        if count == 0 :
            Soldiers = Soldiers[len(Soldiers)-a[1]:] + Soldiers
            count += 1
        else :
            Soldiers = Soldiers[len(Soldiers)-a[1]:] + Soldiers[a_2:]
        a_2 = a[1]
    print('Answer : %d' %Soldiers[0])

def Josephus(hu, inter):
    humans = list(range(1, hu + 1))
    count = 0
    while len(humans) != 1:
        dellist = []
        for args in humans:
            count = count + 1
            if count % inter == 0:
                dellist.append(args)
        for a in dellist:
            del humans[humans.index(a)]
    return humans[0]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Josephus {

    public static int execute(int N, int K){
        // N : 인원수 , K : 간격

        Queue<Integer> queue = new LinkedList<>();

        for(int i=1; i<= N; i++){
            queue.offer(i);
        }
        int count = 1;

        while(queue.size() > 1){

            int order = queue.poll();

            if(count % K == 0){
                count++;
            }else{
                queue.offer(order);
                count++;
            }
        }
        return queue.poll();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();

        sc.close();

        System.out.println(execute(N, K));
    }

}

def slain(n,k):
    soldiers = [i+1 for i in range(n)]
    cursor = 0
    while len(soldiers) > 1 :
        cursor = (cursor + (k-1)) % len(soldiers)
        print("The Next Joseph is : {} ".format(soldiers[cursor]))
        soldiers.pop(cursor)
    else : print("===================\n The Last Survivor is : {}".format(soldiers[0]))

파이썬 3 재귀함수로 짜봤습니다. k가 1일때도, n보다 클때도 성립합니다.

def josephus(n, k):
    def jsps(a, k):
        if len(set(a)) != 1:
            print('start : ', a, ' -> 재귀함수에 입력됨')
            a *= (k-1)//len(a)+1
            print('1st : ', a, ' -> 리스트의 길이가 k보다 길어지도록 세팅')
           r = len(a) % k
            b = [a[i * k - 1] for i in range(1, len(a) // k + 1)]
            print('제거할 숫자 : ', str(b)[1:-1])
            for i in range(len(b)):
                while b[i] in a:
                    a.remove(b[i])
                    if len(a) == 1: return a[0]
            print('2nd : ', a, ' -> 숫자 제거 결과')
            a1 = (a[-r:] + a[:-r])[:len(set(a))]
            print('3rd : ', a1, ' -> 마지막으로 지워진 수 바로 뒤에서부터 시작하도록 재배치', end='\n\n')
            return jsps(a1, k)
        return a[0]
    return jsps(list(range(1, n+1)), k)


print('답 : ', josephus(10, 3))

결과

start :  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  -> 재귀함수에 입력됨
1st :  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  -> 리스트의 길이가 k보다 길어지도록 세팅
제거할 숫자 :  3, 6, 9
2nd :  [1, 2, 4, 5, 7, 8, 10]  -> 숫자 제거 결과
3rd :  [10, 1, 2, 4, 5, 7, 8]  -> 마지막으로 지워진 수 바로 뒤에서부터 시작하도록 재배치

start :  [10, 1, 2, 4, 5, 7, 8]  -> 재귀함수에 입력됨
1st :  [10, 1, 2, 4, 5, 7, 8]  -> 리스트의 길이가 k보다 길어지도록 세팅
제거할 숫자 :  2, 7
2nd :  [10, 1, 4, 5, 8]  -> 숫자 제거 결과
3rd :  [8, 10, 1, 4, 5]  -> 마지막으로 지워진 수 바로 뒤에서부터 시작하도록 재배치

start :  [8, 10, 1, 4, 5]  -> 재귀함수에 입력됨
1st :  [8, 10, 1, 4, 5]  -> 리스트의 길이가 k보다 길어지도록 세팅
제거할 숫자 :  1
2nd :  [8, 10, 4, 5]  -> 숫자 제거 결과
3rd :  [4, 5, 8, 10]  -> 마지막으로 지워진 수 바로 뒤에서부터 시작하도록 재배치

start :  [4, 5, 8, 10]  -> 재귀함수에 입력됨
1st :  [4, 5, 8, 10]  -> 리스트의 길이가 k보다 길어지도록 세팅
제거할 숫자 :  8
2nd :  [4, 5, 10]  -> 숫자 제거 결과
3rd :  [10, 4, 5]  -> 마지막으로 지워진 수 바로 뒤에서부터 시작하도록 재배치

start :  [10, 4, 5]  -> 재귀함수에 입력됨
1st :  [10, 4, 5]  -> 리스트의 길이가 k보다 길어지도록 세팅
제거할 숫자 :  5
2nd :  [10, 4]  -> 숫자 제거 결과
3rd :  [10, 4]  -> 마지막으로 지워진 수 바로 뒤에서부터 시작하도록 재배치

start :  [10, 4]  -> 재귀함수에 입력됨
1st :  [10, 4, 10, 4]  -> 리스트의 길이가 k보다 길어지도록 세팅
제거할 숫자 :  10
2nd :  [4, 4]  -> 숫자 제거 결과
3rd :  [4]  -> 마지막으로 지워진 수 바로 뒤에서부터 시작하도록 재배치

답 : 4

import sys
import numpy as np

def rotate(l,n):
    return (l[-n:] + l[:-n])

width = int(sys.argv[2])

a = np.array([ x for x in range(1,int(sys.argv[1])+1) ])
while len(a) != 2:
    rm_idx = np.array([ x for x in range(width-1,len(a), width) ])
    rotate_count = len(a) - (rm_idx[-1] + 1)
    r = np.delete(a, rm_idx)
    r = np.array(rotate(list(r),rotate_count))
    a = r

l = list(a)
l.pop(0)
print(l)

import java.util.ArrayList;
import java.util.Scanner;

public class JosephusProblem {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt(), temp = k;
        ArrayList<Integer> p = new ArrayList<>();
        for (int i = 0; i < n; i++)
            p.add(i + 1);
        while (p.size() != 1) {
            p.remove(k - 1);
            k += temp - 1;
            while (p.size() < k)
                k -= p.size();
        }
        System.out.println(p);
    }
}

(아래와 같이 짜보긴 했는데, 다른 분들 코드도 훌륭하네요.)

파이썬 3.0

풀이 개요: 모든 값이 1인, 병사의 인원수만큼의 길이를 가지는 리스트를 만듭니다. --> 병사 10명인 경우: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 병사가 죽으면 1을 0으로 만듭니다.

처음 kill_index는 -1로 줍니다. 간격만큼 이동한 후 다른 병사를 죽이는데, 이때 0인 병사(이미 죽은 병사)는 간격 계산에 사용되지 않습니다. 이렇게 반복하다보면 리스트의 합이 1이 되는 순간이 오는데(생존자 1명), 이 아이템의 index에 1을 더한 값이 생존병사의 번호입니다.

def fn(n, k):
    list1 = [1 for i in range(n)] #모든 아이템이 1인, 길이 n의 리스트를 만듦; 죽은 병사는 0으로 표시
    kill_index = -1 #시작 시점

    count = 0
    while count < k:
        kill_index = (kill_index + 1) % n  #다음 인덱스로 이동
        if list1[(kill_index)] == 1:  #살아 있는 병사이면 조건에 따라 죽이거나, count를 1올리고 다음으로 이동하거나
            if count == k - 1:
                list1[(kill_index)] = 0
                if sum(list1) == 1:
                    return list1.index(1) + 1
                    break
                count = 0
            else:
                count += 1
        else:  # 죽어있는 병사의 경우 count를 올리지 않음; 위로 올라가서 그냥 다음 index로 이동
            pass

data = input("총 병사수 한 칸 뛰고 간격 입력:")
data_list = data.split(" ")
n1 = int(data_list[0])
k1 = int(data_list[1])

print(fn(n1, k1))

def josephus(n, k):
    arr = [i for i in range(1,n+1)]
    delindex = k-1
    while len(arr) > 1:
        del arr[delindex]
        delindex = (delindex+k-1)%len(arr)
    return arr[0]
print(josephus(10,3))

def Josephus(N ,K ,m=0):
    cnt = K - m
    sol = range(1,N+1)
    list = []
    while True:
        for i in sol:
            cnt -= 1
            if cnt == 0:
                cnt = K
            else:
                list.append(i)

        if len(list) != 1:
            sol = list
            list = []
        else:
            print (list)
            break


Josephus(10,3)

k=3  #간격
n = [i for i in range(1,11)] #총병사수
def func(n):
    global k
    count = (k-1) #2 -> 1 ->0 
    for j in range(len(n)):
        if count >= len(n):
            if k ==1:
                n.pop(k)
                n.pop(k)
                return print(n)
            k -=1 # 3 ->2 ->1
            func(n)
            return n
        if j== count:
            n.pop(count)
            count +=2 
            print(n)
func(n)
#[1, 2, 4, 5, 6, 7, 8, 9, 10]
#[1, 2, 4, 5, 7, 8, 9, 10]
#[1, 2, 4, 5, 7, 8, 10]
#[1, 4, 5, 7, 8, 10]
#[1, 4, 5, 8, 10]
#[4, 5, 8, 10]
#[4, 5, 10]
#[4]

C#

using System;
using System.Collections.Generic;
using System.Linq;

namespace CD060
{
    class Program
    {
        static void Main()
        {
            int numberOfSolders = 10;
            int skip = 3;
            Console.WriteLine(Josephus(numberOfSolders, skip));
        }

        static int Josephus(int n, int k)
        {
            List<int> solders = Enumerable.Range(1, n).ToList();
            int idx = k;
            while (solders.Count > 1)
            {
                solders.RemoveAt(idx - 1);
                idx += (k - 1);
                if (idx > solders.Count) { idx -= solders.Count; }
            }
            return solders[0];
        }
    }
}

동일 문제에 대해 Josephus Permutation을 적용하여 풀 수도 있는데, Josephus Permuation은 다음과 같이 정의된다:

병사 수 n명(첫번 째 병사에 대해 n = 1), 간격 k이 주어질 때, n과 k의 관계는 다음과 같다.

f(n, k) = {f(n - 1, k) + k - 1} % n + 1

f(1, k) = 1

static int Josephus(int n, int k)
    {
        if (n == 1)
        {
            return 1;
        }
        else
        {
            return (Josephus(n - 1, k) + k - 1) % n + 1;
        }
    }

def josep(n,k):

    n,i = list(range(1,n+1)),0

    while len(n) != 2:
        i += k

        if i >= len(n):
            i %= len(n)
            n = list(x for x in n if x > 0)


        n[i%len(n)-1] = 0

    print(n[0])

N, K = map(int, input().split())

def Josephus(N, K):
    people = list(range(1,N+1))
    M = K - 1
    b = 0
    while len(people) > 1:
        b = (len(people) + b) % K
        del people[M::K]
        M = K - b - 1
    return people[0]

print(Josephus(N, K))

my_list = []
n,k = map(int,input("입력(n,k/ 공백구분):").split(' '))
index_current=0
cycle=0

for i in range(1,n+1):
    my_list.append(i)

while len(my_list)!=1:
    for i in range(len(my_list)):
        index_current+=1 # k와의 배수관계를 알아보기위해 1부터 시작
        if index_current%k==0:
            # 현재 index는 계속 증가하며 k의 배수인지 확인, 다음 라운드에서 인덱스 카운트를 이어서 하기 위함
            del my_list[i-cycle]
            # 요소가 지워져서 index가 하나씩 줄어들기 때문에 한 cycle 안에서는 index를 점차 줄여 삭제
            cycle+=1
    cycle=0
print(my_list[0]) # 마지막 남은 병사

data1 = input("initial data: (예)10 3\n") #숫자사이 공백으로 구분
kt = ''
nt = ''
blank = False
for i in data1 :
    if i == ' ' :
        blank = True
        continue
    elif blank :
        nt += i
    else :
        kt += i
k = int(kt)
n = int(nt)

sol = list(range(1, k + 1))

if n == 1 :
    print("\nanswer:\n", sol[-1])
else :
    i = 0
    while len(sol) > 1 :
        for j in sol :
            i += 1
            if i % n == 0 :
                if sol[-1] == j :
                    i -= 1
                sol.remove(j)
                i += 1
    print("\nanswer:\n", sol[0])

import java.util.ArrayList;
import java.util.*;

public class flexible {

        public static void main(String[] args) {

            Scanner scanf = new Scanner(System.in);
            int first=0, second =0;

            System.out.print("initial data: ");
            first = scanf.nextInt();
            second = scanf.nextInt();

            System.out.println("answer: " + "\n"+dissolve(first, second));
        }

          public static int dissolve(int n, int j) {

                ArrayList <Integer> list_container = new ArrayList<>();
                int index_search = j-1;

                for(int i = 1 ; i <= n ; i++){
                    list_container.add(i);
                }

               for(int i = n - 1 ; i >= 1  ; i--){

                    list_container.remove(index_search);
                    index_search += j-1;
                    if(index_search >= list_container.size()){
                        index_search = index_search % list_container.size();
                    }
                }

                return list_container.get(0);
            }


}

def Josephus_Problem(sub,K):
    if len(sub)==1:
        return sub[0]

    if len(sub)<=K-1:
        del sub[K%len(sub)-1]
        return Josephus_Problem(sub,K)

    del sub[K-1];subb=[]
    for i in range(K-1,len(sub)+2):
        if i>=len(sub):
            subb.append(sub[i-len(sub)])
        else:            
            subb.append(sub[i])

    return Josephus_Problem(subb,K)

n,k=map(int,input("initial data:\n").split());sol=list(range(1,n+1))
print("\nanswer:\n",Josephus_Problem(sol,k))

오래간만에 재귀함수를 이용하여 풀어보았읍니다. 역시 단번에 실행되지 않고 꼭 어딘가에서 오류가 나오는군요. 제가 만든 코드에서는 기저사례가 두개라서 하나만 상정하고 풀었었던지라 깨닫는데에 꽤 머리를 써버렸네요. 그래도 풀려서 재미났읍니다.^^

def main():
    input_file = open("josep.inp", "r")
    output_file = open("josep.out", "w")

    line = input_file.readline().split(" ")
    ransome =[]
    dead_list = []
    result = ""

    ransome_num = int(line[0])+1
    for i in range(1,ransome_num):
        ransome.append(i)

    kill_num = int(line[1])
    count = 0
    while( len(ransome) > 1 ):
        i = 0
        j = 0
        while( i < len(ransome)):
            comp = count + 1
            if( (comp % kill_num) == 0):
                dead_list.append(ransome[i])
                count = count + 1
                i = i +1
            else :
                count = count + 1
                i = i + 1
        while( j < len(ransome)):
            if( ransome[j] in dead_list):
                ransome.remove(ransome[j])
                j = 0
            else:
                j = j + 1
    for i in dead_list:
        result = result +" "+ str(i)

    output_file.write(result.rstrip(" "))

    input_file.close()
    output_file.close()

if __name__ == '__main__':
    main()

package codingDojang;

import java.util.ArrayList; import java.util.List; import java.util.Scanner;

public class Josephus {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner in = new Scanner ( System.in) ;
    int Number = in.nextInt() ;
    int Interval = in.nextInt() ;
    List <String> PList = new ArrayList <String> () ;
    for ( int i = 0 ; i < Number ; i++) {
        PList.add( String.valueOf(i+1)) ;
    }
    int turn = 0 ;

    while ( PList.size() > 1 ) {
        for ( int i = 0 ; i < PList.size() ; i++ ) {
            turn ++ ;
            if ( turn == Interval ) {
                PList.remove(i) ;
                turn = 1 ;
            }
        }
    }
    System.out.println("Result: " + PList.get(0));
    in.close();
}

} ```

N = int(input("포로수를 입력하시오 : ")) K = int(input("몇번째 부터 죽일 건가요? : "))

member = [] killmember = []

for i in range(1, N+1): member.append(i)

count = 1

while len(member) != 1: for i in member : if count % K == 0: killmember.append(i) count += 1

for j in killmember:
    member.remove(j)
killmember = []

print(member[0])

Python 3.7

def jsp(n, k):
    a = list(range(1, n+1))
    k -= 1
    ov = 0
    for i in range(1, n):
        ov += (i*k - ov)//len(a) * len(a)
        del a[i*k - ov]
    return a[0]

시간복잡도 O(n)

N = 10, k = 3이라고 하면, 리스트 a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 내에서 3번째(a[2]) 숫자 3을 지웠을 때 a = [1, 2, 4, 5, 6, 7, 8, 9, 10] 다음 숫자 6은 5번째(a[4])가 됩니다. a = [1, 2, 4, 5, 7, 8, 9, 10] 그리고 그 다음 숫자 9는 7번째(a[6])가 됩니다. 즉 처음에 a[k-1]로 인덱싱 하고, 다음 단계로 진행할 때 마다 k-1씩 더해서 인덱싱 하면 됩니다. a[k-1], a[2(k-1)], a[3(k-1)].

a = [1, 2, 4, 5, 7, 8, 10] 4번째에서 len(a) = 7이고, a[4(3-1)] = a[8]이 되어서 오버가 됩니다. 이때 len(a)를 빼서 인덱싱하면 a[1]을 인덱싱할 수 있습니다. 원리는 (4(3-1))%(10-3) = 8%7 = 1이 되는 원리입니다.

def jsp(n, k):
    a = list(range(1, n+1))
    re = 0
    for i in range(1, n):
        re = (re + k-1)%len(a)
        del a[re]
    return a[0]

나머지만 저장하는 방식으로 인덱싱 할 수도 있습니다.

n = int(input("총인원수 : "))
k = int(input("간격 : "))

List = list(i for i in range(1, n+1))
Result = list(i for i in range(1, n+1))
rm_List = []
len_rm_List =0
count = 0
i = -1
init = 0
while True :
    if len_rm_List == n-1:
        break
    i = i + 3 - init

    if i < len(List):
        rm_List.append(List[i])        
        init = 0
        count+=1
    else :
        init = len(List) - (i-k+1)
        for i in range(count):
            List.remove(rm_List[i])
        print("Result : ", List)
        len_rm_List += count
        rm_List =[] # 초기화
        count =0        
        i = -1 # i 초기화

#include <iostream>
#include <vector>
using namespace std;
/*
약 2,000년 전에는 전쟁에서 병사들이 적들에 의해 동굴에 갇히게 되는 경우가 종종 있었다고 한다.
그들은 포로가 되는것을 방지하기 위해 동그랗게 서서 마지막 한 사람이 남을 때 까지 순서대로 돌아가며 세번째에 해당되는 사람을 죽여 나갔다고 한다.
마지막으로 남게되는 사람은 자살하기로 약속되어 있었지만 보통 적들에게 항복을 하는 경우가 많았다고 한다.

여러분이 풀어야 할 문제는 총 인원수(N)와 간격(K)이 주어졌을 때 가장 마지막에 살아남는 병사의 위치(the safe position)를 알아내는 것이다.
*/

void Func(int n, int k) {
    cout << n << "명의 사람중" << k << "번째 사람을 죽여나간다.. 한명만 살아남을 때까지..." << endl;
    int count = 1;
    vector<int> v;
    vector<int> r;

    for (int i = 1; i <= n; i++)
        v.push_back(i);
    while (1) {
        cout << "인원수" << v.size() << endl;
        if (v.size() == 1)break;
        for (int i = 0; i < v.size(); i++) {
            if (count == 3) { cout << "(" << v[i] << ") "; count = 1; continue; }
            else { cout << v[i] << " "; r.push_back(v[i]); }
            count++;
        }
        cout << endl;

        v.clear();
        for (int i = 0; i < r.size(); i++)
            v.push_back(r[i]);  
        r.clear();
    }
    cout << "살아남은 1인" << v.front() << "번 째사람" << endl;
}

int main() {
    Func(10, 3);
}

n=int(input('N='))
k=int(input('K='))
sol=[]

for i in range (1,n+1):
   sol.append(i) 
i=0
while (len(sol)>1):
    i+=k
    while(i>len(sol)):
        i-=len(sol)
    del sol[i-1]
    i-=1

print('\nanswer :',sol[0])

# 파이썬

n=int(input('N='))
k=int(input('K='))
sol=[]

for i in range (1,n+1):
   sol.append(i) 
i=0
while (len(sol)>1):
    i+=k
    while(i>len(sol)):
        i-=len(sol)
    del sol[i-1]
    i-=1

print('answer :',sol[0])

from collections import deque

def jose(n, k):
    soldier = deque([i for i in range(1, n+1)])
    while len(soldier) != 1:
        deque.rotate(soldier, -(k-1))
        deque.popleft(soldier)
    return soldier[0]

def main():
    n, k = 10, 3
    print('initial data: \n{} {}\n\nanswer: \n{}'.format(n, k, jose(n, k)))

if __name__ == '__main__':
    main()

N=int(input("병사 인원 : "))
K=int(input("간격 : "))
per=[]
value=[]
for i in range(N):
    per.append(i+1)
j=0
count=1
while len(per)!=1:
    if j>=len(per):
        j=0
        for i in value:
            per.remove(i)
        value=[]
        print("Round : {}".format(per))
    if count==K:
        value.append(per[j])
        count=0
    j+=1
    count+=1

def Josephus(n, k): # n은 병사, k는 간격
    nlist = []
    die_list = []
    for i in range(1, n+1):
        nlist.append(i)
    print(nlist)

    n = 1
    while len(nlist) != 1: # 병사가 한명 나을 때까지 계속 반복
        for i in nlist:
            print(n)
            if n % k == 0:
                die_list.append(i)
            n += 1

        for j in die_list:
            nlist.remove(j)
            die_list = []

    print(nlist)


Josephus(10, 3)

참조하여 만들었습니다.

def josephus_prob(n, k):
    nums_list = list(range(1, n + 1))
    count = 0
    while len(nums_list) > 1:
        should_delete_list = [nums_list[i] for i in range(len(nums_list)) if (count + i + 1) % k == 0]
        count += len(nums_list)
        for person in should_delete_list:
            nums_list.remove(person)
    return nums_list[0]

def Josephus(n,k):
    a = list(range(1,n+1))
    m = k - 1
    b = 0
    while len(a) > 1:
        b = ((len(a)+b)%k)
        del a[m::k]
        m = k - b - 1
    return a

print (Josephus(10,3))

package test;
import java.util.*;


public class Test{
     public static void main(String args[]) {
         int i = 1;
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         int k = sc.nextInt();

         ArrayList<Integer> list = new ArrayList<Integer>();

         for(int j = 0; j < n; j++)
             list.add(j+1);

         while(list.size() > 1) {
             Iterator<Integer> iterator = list.iterator();
             while(iterator.hasNext()) {
                 iterator.next();
                 if(i % k == 0)
                     iterator.remove();
                 i++;
             }
         }
         System.out.println(list.get(0));
         sc.close();
    }
}

import java.util.*;

public class test9 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("병사 수를 입력하시오 : ");
        int N = scanner.nextInt();
        System.out.print("간격을 입력하시오 : ");
        int K = scanner.nextInt();

        ArrayList<Integer> Soliders = new ArrayList<>();

        for (int a = 1; a <= N; a++) Soliders.add(a);
        for (int a = 1; a < Soliders.size(); a++) {
            if(a % K == 0) System.out.println("사망한 병사 : "+Soliders.get(a-1));
            else Soliders.add(Soliders.get(a-1));
        }

        System.out.println("생존한 병사 : "+Soliders.get(Soliders.size()-1));
    }
}

일단 테스트케이스는 통과하는데 맞으려나요

import copy
N,K=map(int, input("병사수와 간격을 입력하세요 : ").split())
def Alive (N,K) :
    l = list(range(1,N+1))
    ll = copy.copy(l)
    s = set(ll)
    i=0
    while len(s) > 1 :
        i+=1
        if i%K == 0 :
            ll.remove(l[(i-1)])
        if i == len(l) :
            s=set(ll)
            l+=ll

    print(list(s)[0])

Alive(N,K)

def josephus(n,k):
    people = [i for i in range(1,n+1)]
    while 1:
        if len(people)==1:
            print(people)
            break
        if k > len(people):
            k = k - len(people)
        del people[k-1]
        k += 2


josephus(10,3)

lists = {}
def circle(n):
    for i in range(1, int(n)+1):
        lists[i] = 1
    # print(lists)

def alive():
    alive = []
    for aa in lists.keys():
        if lists[aa] == 1:
            alive.append(aa)
    return alive

def kill(k):
    temp = []
    remainder = 0
    lst_idx = 0
    number_alive = len(alive())
    while(number_alive > 1):
        # call alive list
    # for j in range(5):
        temp = alive()
        count = 0
        for i in range(1, len(temp)+1):
            try:
                if (int(i)+remainder) % k == 0:
                    lists[temp[i-1]] = 0
                    # print(temp[i-1], 'was killed')
                    count += 1
                    lst_idx = i
            except: pass
        remainder = len(temp) - lst_idx
        number_alive = len(temp) - count
        # print(alive(), remainder, number_alive)

def suicide():
    s = input('initial data: ')
    n, k = s.split()
    # print(n,k)

    circle(int(n))
    # print(alive())

    kill(int(k))
    print('answer:', alive()[0])

suicide()

def Josephus(a,b):
    count=0
    c=[]
    for i in a:
        count+=1
        if count%b==0:
            if len(set(c))==len(set(a))-1:
                pass
            else:
                c.append(a[count-1])
        else:
            a.append(a[count-1])
    a_sub_c = [x for x in a if x not in c]
    print("생존자는 : {}번째 사람입니다".format(set(a_sub_c)))


Josephus(list(range(1,(int(input("생존자를 입력하세요 : "))+1))),b=int(input("간격을 입력하세요 : ")))

def josephus(n, k, init=0):
    if str(n).isnumeric():
        list1 = [i for i in range(1, n+1)]
    else:
        list1 = n
    ct = 0
    list2 = []
    if init != 0:
        cs = k - init
    else:
        cs = 0
    for num1, num2 in enumerate(list1):
        if (num1 + 1) % k == cs:
            ct = 0
        else:
            list2.append(list1[num1])
            ct += 1
    print(list2)
    if len(list2) == 1:
        print("최종생존자는 : ", str(list2[0]))
    else:
        josephus(list2, k, ct)


josephus(10, 3)

결과
[1, 2, 4, 5, 7, 8, 10]
[1, 4, 5, 8, 10]
[4, 5, 10]
[4, 10]
[4]
최종생존자는 : 4

#codingdojing_Josephus Problem

from collections import deque

N, K = map(int, input("initial data: ").split())    #10 3

people = [i for i in range(1,N+1)]  #[0 ~ 9]
index = K-1

while len(people) > 1:
    people.pop(index)       #1명 제거
    N -= 1                  #총 인원수 감소
    index = (index+K-1)%N   #다음 세번째 사람은, 새로운 리스트에서 K-1 다음사람
    print(people)

print(f"answer: \n{people[0]}")

#deque 사용하는 방법

N, K = map(int, input("initial data(deque Ver.): ").split())

people_deque = deque([i for i in range(1, N+1)])

while len(people_deque) > 1:
    people_deque.rotate(1-K)    # 왼쪽으로 K-1칸씩 이동 
    people_deque.popleft()
    print(people_deque)

print(f'answer: \n{people_deque[0]}')

리스트 크기를 줄이며 index로 없애는 방법과, deque를 이용하는 방법 두 가지로 작성해보았습니다.

input=input("initial data:\n")
N,K=map(int,input.split())
i=2
list=range(1,N+1)
copylist=list[:] #본래 리스트의 인덱스를 유지하며 수를 제거하기 위해 복사한 리스트
while True:
    list.remove(copylist[i])
    print(list)
    if len(list)==1: break
    i+=K
    if i>=len(copylist):
        i=i-len(copylist[:]) #남은 개수를 고려하여 i를 초기화
        copylist=list[:] #copylist 재설정
print("answer:\n%d"%list[0])

def Josephus_Problem(N,K):
    soldiers = list(range(1,N+1))
    a = 1
    while True:
        if len(soldiers) == 2:
            break
        elif a == K:
            del soldiers[0]
            a = 1
            continue
        else:
            soldiers.append(soldiers[0])
            del soldiers[0]
            a += 1
            continue
    return soldiers[1]

if __name__ == '__main__':
    N,K = map(int, input().split()) 
    print(Josephus_Problem(N,K))

n = int(input("병사수를 입력하시오"))

k = int(input("k값을 입력하시오"))


def solution(a,k):
    arr = []
    for i in range(1,a+1):
        arr.append(i)

    m=0
    while len(arr) !=1:
        al = len(arr)
        try:
            j=1
            while True:
                arr.pop((k-1)*j-m)
                j+=1
        except IndexError:
            m= (al+m)%k
    return print(arr[0])


solution(n,k)

#입력
_input = input("initial date : ").split()
_N= int(_input[0])
_K= int(_input[1])


#풀이2
rest = 0
while len(Nlist) != 1 :
    Nlist = [Nlist[i] for i in range(0,len(Nlist)) if (i+1+rest) % _K == 0]
    rest = len(Nlist) % _K
print("result :",Nlist)

// Rust

// cursor(remove index) 초기 위치는 k-1, 증가 폭은 k-1(하나씩 제거되므로), vector 길이보다 커지면, vector 길이를 빼줌

fn josephus(n: usize, k: usize) -> usize {

let mut vec: Vec<usize> = (1..n+1).collect();
let mut cursor = k - 1;
while vec.len() > 1 {
    vec.remove(cursor);
    cursor += k - 1;
    if cursor >= vec.len() {
        cursor -= vec.len();
    }
}
vec[0]

}

[test]

fn test() {

assert_eq!(josephus(10, 3), 4);

}

def jos(s,k):
    seq = [x for x in range(1, s+1)]
    n=1

    while len(seq)>1:
        seq= [seq[1:]+[seq[0]],seq[1:]][n%k == 0]
        n+=1
    return seq[0]    

jos(10,3)

변수이름을 아직 익숙하지 않아 마구 설정했습니다.

n=int(input('몇 명?'))
k=int(input('몇 번째 사람?'))

round0=[i for i in range(1,n+1)] #1~n

while len(round0)!=k:
    x=len(round0)
    for i in round0[k-1::k]:
        round0.remove(i) #k번째 사람들 제거
    round0=round0[-(x%k):]+round0[:-(x%k)] #제거한 사람의 뒷부분을 앞부분으로 옮김.
#k명만 남은 이후론 한명씩 빠짐.
while len(round0)>1:
    y=len(round0)
    round3=round0*k #k명보다 적으면 k번째 사람을 제거할 수 없어서 작성.
    z=round0.index(round3[k-1])
    round0=round0[z+1:]+round0[:z] #제거한 사람의 뒷부분을 앞부분으로 옮김.
print(round0)

deque를 활용해봤습니다.

from collections import deque

def josephus(n,k):
    SURVIVOR = deque(list(range(1,n+1)))
    while len(SURVIVOR) > 1:
        SURVIVOR.rotate(-k+1)
        del SURVIVOR[0]
    return SURVIVOR

print(josephus(10,3))

python 3.10입니다. 맨 앞의 병사를 맨 뒤로 옮기는 것을 반복하다가 차례가 되면 삭제하는 방식을 사용하였습니다. 다음은 코드입니다.

N, K = [int(num) for num in input("initial data:\n").split()]
a = list(range(1, N+1))
for _ in range(N-1):
    for _ in range(K-1): a.append(a.pop(0))
    del a[0]
print(f"answer:\n{a[0]}")

다음은 실행 결과입니다.

initial data:
10 3
answer:
4

N = int(input("병사의 수를 입력하시오 :"))            #병사 수 입력받기
K = int(input("간격을 선택하세요 :"))               #간격 입력받기

soldier_list = []
soldier_list1 = []
soldier_list2 = []

num = 1

for i in range(1, N+1):                         #병사 리스트 생성
    soldier_list.append(i)

while True:

    if len(soldier_list) == 1:                      #병사가 한명 남은경우 출력
        print(soldier_list[0])

        break

    for n in range(0, len(soldier_list)):           #3번째 병사 제거하는 알고리즘
        if n == K * num - 1:
            soldier_list1.append(soldier_list[n])
            num += 1

        else:
            soldier_list2.append(soldier_list[n])

    del soldier_list[:K * (num - 1)]

    for i in soldier_list2:                         #죽은병사 리스트와 살아있는 병사 리스트 비교해서 중복된경우 제거
        if i in soldier_list1:
            soldier_list2.remove(i)

    if soldier_list2[0] == soldier_list2[-1]:       #살아있는 병사 리스트에 첫번째와 마지막 번째 비교해서 중복인경우 방지
        if len(soldier_list2) == 1:
            pass
        else:
            del soldier_list2[0]

    soldier_list = soldier_list + soldier_list2     #살아있는 병사 리스트 새로 생성
    soldier_list1 = []                              #리스트 초기화
    soldier_list2 = []
    num = 1