[Python] 코딩 도장 - Josephus Problem
Updated:
코딩 도장 사이트의 문제를 직접 풀어본 내용을 정리하여 올립니다.
코딩 도장에서 여러 문제를 확인할 수 있습니다.
난이도 순으로 차근차근 풀어보려 합니다.
[문제: Josephus Problem] - Lv.2
약 2,000년 전에는 전쟁에서 병사들이 적들에 의해 동굴에 갇히게 되는 경우가 종종 있었다고 한다.
포로가 되는것을 방지하기 위해 동그랗게 서서 마지막 한 사람이 남을 때 까지 순서대로 돌아가며 세번째에 해당되는 사람을 죽였다.
마지막으로 남게되는 사람은 자살하기로 약속되어 있었지만 보통 적들에게 항복을 하는 경우가 많았다고 한다.
풀어야 할 문제는 총 인원수(N)와 간격(K)이 주어졌을 때 가장 마지막에 살아남는 병사의 위치를 알아내는 것이다.
예를 들어 병사수가 총 10명이고 돌아가며 세번째에 해당되는 병사를 제거하는 경우는 다음과 같다:
N = 10, K = 3
위의 경우 다음과 같은 순서로 병사들이 제거된다. (괄호는 제거되는 병사를 의미한다)
1st round: 1 2 (3) 4 5 (6) 7 8 (9) 10
2nd round: 1 (2) 4 5 (7) 8 10
3rd round: (1) 4 5 (8) 10
4th round: 4 (5) 10
5th round: 4 (10)
위 예에서 끝가지 살아남는 병사는 4, 즉 4번째 병사이다.
입력 데이터는 총 병사수 N과 간격 K이다.
출력 데이터는 마지막까지 살아남는 병사의 위치이다.
(단, 최초 시작은 1번 병사부터이다.)
입출력 예는 다음과 같다:
initial data:
10 3
answer:
4
출처: https://codingdojang.com/scode/447?answer_mode=hide
[풀이]
def Josephus_Problem():
n, k = [int(i) for i in input("initial data:").split()]
a = list(range(1,n+1))
while a[-1] != a[-2]:
del_v = [v for i,v in enumerate(a) if (i+1) % k == 0]
a = a + sorted(list(set(a)-set(del_v)))
return print("answer:", a[-1])
Josephus_Problem()
initial data:10 3
answer: 4
이 문제는 간격 k가 매 차례마다 리셋이 되는게 아니라서 전 차례의 나머지를 고려해야한다.
처음엔 간격 k로 나눠지는 인덱스를 제거하고 나머지를 계산해 다음 차례에 인덱스에 나머지를 플러스 하는 방식을 생각했다.
그런데 만약 간격이 4인데 2개가 남았다면 다시 2개를 추가한후 4번째가 제거 될 것이다.
이런 이유 때문에 문제 예시를 응용해 리스트를 추가하는 방식으로 작성하였다.
[v for i,v in enumerate(a) if (i+1) % k == 0]를 통해 매 차례 제거되는 병사의 값을 구한다.
sorted(list(set(a)-set(del_v)))로 남은 병사를 구한 후 원래 리스트에 추가해준다.
이 방법을 사용하지 않고 단순히 나누기만 하면 원하는 형태로 리스트에 추가하기가 어렵다.
반복을 계속해서 리스트의 마지막 숫자와 그 앞 숫자가 같으면 종료한다.
def Josephus_Problem():
n, k = [int(i) for i in input("initial data:").split()]
a = list(range(1,n+1))
while a[-1] != a[-2]:
del_v = [v for i,v in enumerate(a) if (i+1) % k == 0]
a = a + sorted(list(set(a)-set(del_v)))
print(sorted(list(set(a)-set(del_v))))
return print("answer:", a[-1])
Josephus_Problem()
initial data:12 4
[1, 2, 3, 5, 6, 7, 9, 10, 11]
[1, 2, 3, 6, 7, 9, 11]
[1, 2, 6, 7, 9]
[1, 2, 6, 9]
[1, 2, 9]
[1, 2]
[1, 2]
[1]
[1]
answer: 1
앞서 예를 들었던대로 마지막에 1,2가 2번 나오는 케이스가 있다.
[추천 풀이]
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))
[4]
일단 너무 간결해보여서 마음이 아프다.
이 분은 제거하면서 매 차례마다 시작 인덱스를 바꿔주는 방식을 사용했다.
def Josephus(n,k):
a = list(range(1,n+1))
m = k - 1
b = 0
while len(a) > 1:
b = ((len(a)+b)%k) # 매 차례 나머지
print(a, "시작 인덱스:", m)
del a[m::k]
m = k - b - 1
return a
print(Josephus(12,4))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 시작 인덱스: 3
[1, 2, 3, 5, 6, 7, 9, 10, 11] 시작 인덱스: 3
[1, 2, 3, 6, 7, 9, 11] 시작 인덱스: 2
[1, 2, 6, 7, 9] 시작 인덱스: 3
[1, 2, 6, 9] 시작 인덱스: 2
[1, 2, 9] 시작 인덱스: 2
[1, 2] 시작 인덱스: 3
[1, 2] 시작 인덱스: 1
[1]
여기서 1,2를 보면 시작 인덱스가 3인데 나는 이 경우 인덱스가 없기에 오류가 뜰거라 예상했다.
그래서 굳이 리스트를 계속 더해주는 방식을 사용하였는데 이 분은 결과가 잘 나온다.
a[m::k] 코드에서 [시작:끝:증감]인건 알고 있는데 오류가 안생겨 자세히 확인하려 한다.
a=[1,2]
print(a[0::4])
print(a[1::4])
print(a[2::4])
print(a[3::4])
print(a[6::4])
[1]
[2]
[]
[]
[]
보면 시작이 0,1인 경우는 당연히 잘나타나는데 3,6인 경우 그냥 빈 값을 반환한다.
원래 리스트의 길이보다 큰 인덱스를 사용해도 아무런 문제가 없다.
그래서 제거 방식으로 슬라이싱을 사용하신 것 같다.
n,k=list(map(int,input().split()))
s = list(range(1,n+1))
cursor = 0
while len(s)>1:
cursor = (cursor+k-1)%len(s)
s.pop(cursor)
print(s)
12 4
[1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12]
[1, 2, 3, 5, 6, 7, 9, 10, 11, 12]
[1, 2, 3, 5, 6, 7, 9, 10, 11]
[1, 2, 3, 6, 7, 9, 10, 11]
[1, 2, 3, 6, 7, 9, 11]
[1, 2, 6, 7, 9, 11]
[1, 2, 6, 7, 9]
[1, 2, 6, 9]
[1, 2, 9]
[1, 2]
[1]
또 다른 풀이 방식인데 이분은 매 차례마다 여러 숫자를 지우는게 아니라 하나씩 지워나간다.
정말 참신한 생각이 많다..
Leave a comment