[js] 요세푸스 문제 / 요세푸스 순열_Josephus Problem

[문제 설명]

1번부터 N번까지의 사람이 동그랗게 모여서 앉아있습니다.

1번 부터 순서를 세어 K번째 사람을 모임에서 제외시킵니다.

남은 N-1명에서 이번에 제외된 다음 사람부터 원을 따라 다시 순서를 세서 K번째 사람을 모임에서 제외하는 과정을 마지막 사람이 남을때까지 반복합니다.

이때 마지막으로 남는 사람의 번호를 구하는 프로그램을 구현하세요.

입력 형식

• N: 원형으로 모여있는 사람의 수
• K: 매번 제외시킬 사람의 순서

출력 형식

• 마지막에 남는 사람의 번호를 정수로 반환

제약 사항

• 1 <= N, K <= 100

입출력 예시

• 입력
  • N = 7
  • K = 3
• 출력: 4
• 설명: 1, 2, 3, 4, 5, 6, 7에서 시작하여, 3, 6, 2, 7, 5, 1순서로 제외되어 마지막에는 4번 사람이 남게 된다.

 

 

 

 

[문제 풀이]

function solution(N, K) {
    let Nlist = Array(N).fill(1).map((key, idx) => key + idx);
    let n = [];
    let cnt = 1;
    while (Nlist.length > 0) {
        let data = Nlist.shift();
        if (cnt % K == 0) n.push(data);
        else Nlist.push(data);
        cnt++;
    }
    return n.slice(-1)[0];
}

 

 

 

 

[해설]

요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)이라고 불리는 문제입니다.

우선 Nlist에 1부터 N까지 연속된 수를 갖는 배열을 만들었습니다.

* Array(size).fill(start).map((key, idx) => key + idx);

size에 배열의 크기를, start에 시작 숫자를 넣고 map으로 연속된 배열을 만듭니다.

빈 리스트 n은 큐라고 생각하시면 됩니다.

 

 

Nlist의 길이가 0이 될 때까지 반복문을 돌려줍니다.

1. Nlist에서 shift로 가장 첫 숫자를 빼줍니다.

2-1. 만약 cnt가 K로 나누어떨어진다면 (K번째라면) 정답 배열에 그 값을 넣습니다.

2-2. 만약 K번째가 아니라면 Nlist의 마지막에 값을 다시 넣고, cnt의 값을 1 올려줍니다.

 

즉, 아래와 같이 진행되기 때문에 n에는 정상적으로 요세푸스 수열이 담겨지게 됩니다.

cnt = 1 / data = 1 / Nlist = [2, 3, 4, 5, 6, 7, 1]
cnt = 2 / data = 2 / Nlist = [3, 4, 5, 6, 7, 1, 2]
cnt = 3 / data = 3 / Nlist = [4, 5, 6, 7, 1, 2]		/ n = [3]
cnt = 4 / data = 4 / Nlist = [5, 6, 7, 1, 2, 4]		/ n = [3]
cnt = 5 / data = 5 / Nlist = [6, 7, 1, 2, 4, 5]		/ n = [3]
cnt = 6 / data = 6 / Nlist = [7, 1, 2, 4, 5]		/ n = [3, 6]
cnt = 7 / data = 7 / Nlist = [1, 2, 4, 5, 7]		/ n = [3, 6]
cnt = 8 / data = 1 / Nlist = [2, 4, 5, 7, 1]		/ n = [3, 6]
cnt = 9 / data = 2 / Nlist = [4, 5, 7, 1]		/ n = [3, 6, 2]
cnt = 10 / data = 4 / Nlist = [5, 7, 1, 4]		/ n = [3, 6, 2]
cnt = 11 / data = 5 / Nlist = [7, 1, 4, 5]		/ n = [3, 6, 2]
cnt = 12 / data = 7 / Nlist = [1, 4, 5]			/ n = [3, 6, 2, 7]
cnt = 13 / data = 1 / Nlist = [4, 5, 1]			/ n = [3, 6, 2, 7]
cnt = 14 / data = 4 / Nlist = [5, 1, 4]			/ n = [3, 6, 2, 7]
cnt = 15 / data = 5 / Nlist = [1, 4]			/ n = [3, 6, 2, 7, 5]
cnt = 16 / data = 1 / Nlist = [4, 1]			/ n = [3, 6, 2, 7, 5]
cnt = 17 / data = 4 / Nlist = [1, 4]			/ n = [3, 6, 2, 7, 5]
cnt = 18 / data = 1 / Nlist = [4]			/ n = [3, 6, 2, 7, 5, 1]

 

 

 

 

[느낀점]

이 문제 해결하느라 꽤 오랜 시간이 소요됐습니다.. ㅠㅠ 

처음에는 요세푸스 문제라는 것을 모르고 (이 문제는 따로 프로그래밍 스쿨에서 나온 문제라 제목이 없었거든요)

직접 해설마냥 결과값을 하나하나 적어가며 알고리즘을 생각하고, 구현에 성공했는데 알고보니 이게 요세푸스 수열이라는 문제더라구요...?

요세푸스 문제라는걸 깨닫고 다른 분들 코드를 보니 거의 유사해서 뿌듯했습니다.

순열 문제도 자주 찾아서 풀어봐야겠어요.

 

 

 

[github] - JosephusProblem.js

https://github.com/yh725k/javascript.git

GitHub - yh725k/javascript