[Python] LL P1158 요세푸스 문제

1. 문제 : https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

2. 문제 풀이

    (1) 야나의 첫 번째 문제 풀이

N,K = map(int,input().split()) 
#스페이스로 구분된 두 수 입력받아 정수형 변환

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

popNo = K-1
#popNo번째 자리 수를 pop할 예정임으로 K번째 수를 컴퓨터 자릿수에 맞게 변환반영
result = []
#추출할 값을 받아낼 빈 리스트 생성

while len(josephus) : #josephus 리스트에 남아있는 수가 있는동안
                      #josephus 리스트에 남아있는 수가 없다면 반복 종료
    if popNo >= len(josephus):
        #만약 뽑아낼 자릿수가 전체 리스트의 길이보다 크다면
        popNo = popNo % len(josephus)
        #뽑아낼 자릿수를 전체 리스크 길이로 나눈 몫을 반환함으로써,
        #한바퀴 돌고 처음부터 다시 센 자릿수를 반환한다.
        #고로, 전체 리스트 길이보다 popNo가 작아졌음으로 else조항으로 이동한다.

    else :
        result.append(str(josephus.pop(popNo)))
        #리스트상 popNo번째 자리에 위치하는 숫자를 추출하여 순서대로 리스트화 
        popNo += (K-1)
        #popNo가 if 조항으로 변경됬을 가능성이 있으니 K-1로 다시 복구시킨다.

print("<",", ".join(result),">",sep="")

위 코드가 자꾸 "틀렸습니다"라고 떠서 또다른 풀이로 접근해서 풀었는데... 결론은 출력값 사이에 ", "가 아닌 ","만 넣었기에 발생한 문제였다. 출력을 항상 유의하자.

    (2) 야나의 두 번째 풀이

N,K = map(int,input().split()) 
#스페이스로 구분된 두 수 입력받아 정수형 변환

josephus = [i for i in range(1,N+1)]
# 처음 앉을 때 몇번째 자리에 앉았는지 번호 부여하여 리스트화

popNo = 0
result = []

while len(josephus) > 0: #josephus 리스트에 잔여 값이 있는동안 실행하라
    popNo = (popNo + (K-1)) % len(josephus)
    #빼낼 숫자 자릿수 = (이전에빼낸 숫자 자릿수 + K만큼 추가로 이동)한 숫자를 
    #리스트에 존재하는 총 숫자 갯수로 나눈 몫(한바퀴 돌았다면 돌고 난 후의 자릿수)
    result.append(str(josephus.pop(popNo)))
    #리스트상 popNo번째 자리에 위치하는 숫자 추출하여 순서대로 리스트화 

print("<",", ".join(result),">",sep="")

 

    (3) deque를 이용하는 풀이(작성 예정)

#다른사람들의 풀이를 보고 확인후 추가 예정이다.