This problem takes its name by arguably the most important event in the life of the ancient historian Josephus: according to his tale, he and his 40 soldiers were trapped in a cave by the Romans during a siege.
Refusing to surrender to the enemy, they instead opted for mass suicide, with a twist: they formed a circle and proceeded to kill one man every three, until one last man was left (and that it was supposed to kill himself to end the act).
Well, Josephus and another man were the last two and, as we now know every detail of the story, you may have correctly guessed that they didn't exactly follow through the original idea.
You are now to create a function that returns a Josephus permutation, taking as parameters the initial array/list of items to be permuted as if they were in a circle and counted out every k places until none remained.
Tips and notes: it helps to start counting from 1 up to n, instead of the usual range 0..n-1; k will always be >=1.
For example, with n=7 and k=3 josephus(7,3) should act this way.
[1,2,3,4,5,6,7] - initial sequence
[1,2,4,5,6,7] => 3 is counted out and goes into the result [3][1,2,4,5,7] => 6 is counted out and goes into the result [3,6][1,4,5,7] => 2 is counted out and goes into the result [3,6,2][1,4,5] => 7 is counted out and goes into the result [3,6,2,7][1,4] => 5 is counted out and goes into the result [3,6,2,7,5][4] => 1 is counted out and goes into the result [3,6,2,7,5,1][] => 4 is counted out and goes into the result [3,6,2,7,5,1,4]
So our final result is:
josephus([1,2,3,4,5,6,7],3)==[3,6,2,7,5,1,4]
(요약)주어진 배열에서 k만큼 이동 후 그 요소를 뽑아서 배열에 추가하는 것을 반복해서 나온 배열을 return
.
function josephus(items,k){ const answer = []; const length = items.length; let index = k > length ? (k % length) - 1 : k - 1; for(let i = 0; i < length - 1; i++) { answer.push(items.splice(index, 1)[0]); for(let j = 0; j < k - 1; j++) { index++; if(index >= items.length) { index -= items.length; } } } if(items.length) answer.push(items[0]); return answer; }
첫번빼로 뽑을
index
를 구하는데k
가 배열 길이보다 긴 상황도 있어서 조건을 붙임.이중 반복문을 돌면서 바깥쪽에서는 해당 인덱스의 요소를 뽑아서
answer
에 넣음.안쪽 반복문에서는
index
를 증가시키다가 배열 끝에 닿으면 처음으로 돌아가서 다시index
를 찾음.배열에 요소가 한 개 남을 때까지 찾고 마지막 요소를
answer
에 넣음.마지막 요소만 따로 처리하는 이유는 배열 끝에서 처음으로 돌리는 과정에서
index
가 정상 처리가 안되는 경우가 있어서 따로 했음.