문제

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

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

예시

  • 입력: 7, 3
  • 출력: [3, 6, 2, 7, 5, 1, 4]

1. list로 풀기

예시대로 3번째 마다 사람을 제거하려면, 처음에는 시작점이니 2번만 인덱스를 이동하고 제거한 후 이 후에는 3번 인덱스를 이동해서 제거한다.

첫 시작을 0이 아닌 -1로 시작하는 점에 유의하자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def josephus(n,k):
    res = []
    line = [1 for _ in range(n)] # 값이 1이면 제거 대상, 0이면 제거 완료
    i = -1

    for _ in range(n-1):
        count = 0
        while count < k:
            i = (i + 1) % n # i는 0~6까지 순회해야하므로 나머지로 계산한다.
            if line[i]: # line의 원소가 0이 아니면...
                count += 1
        line[i] = 0
        res.append(i+1)

    res.append(line.index(1)+1)
    return res
  1. line 배열을 1로 초기화 해준다. 1은 아직 제거안된 요소이고 0은 제거된 요소로 처리
  2. 마지막 1개가 남을 때 까지 반복하므로 n-1회 반복한다.
  3. count 변수는 제거되지 않은 원소를 지나온 순서를 카운팅하기 위해 사용한다.
  4. 0 ~ 6까지 index가 순회해야하므로, n으로 나눈 나머지 값을 이용한다.
  5. i를 순회하면서 line의 요소가 0이 아니면, 즉 아직 제거되지 않았으면 순서를 카운팅 해준다.
  6. 순서를 카운팅 해서 k번째 순서에 도달하면, 반복을 멈추고 해당 index 요소를 0으로 바꾼다. (요소 제거)
  7. 해당 index는 0부터 시작했으므로, 결과 배열에 넣어줄 땐 +1을 해준다. 왜냐하면 문제에선 1부터 시작한다 했으니 때문이다.
  8. 이렇게 n-1번 반복하게되면 line의 요소는 1개 남는다. 이 때는 index 메서드를 사용하여 1인 요소의 index를 구한 뒤 결과배열에 추가한다. 이 때도 + 1 을 해줘야한다.