[백준 1158번] 요세푸스 문제 Python 풀이

Python 문제풀이

#요세푸스 문제
a,b = map(int, input().split()) # a는 인원수, b는 삭제되는 자리 위치

x = []
result =[]
# 편하게 리스트에 사람들을 세움
for i in range(a):
    x.append(i)

#count는 삭제되는 자리위치를 셀 변수, current는 현재 위치
count=1
current=-1 #시작마다 current를 1씩 증가시켜 주기 위해 완전 초기 시작은 -1

while 1:
    #만약 1명밖에 남지 않았다면 그사람 출력하고 종료
    if len(x)==1:
        result.append(x[0]+1)
        break
    #만약 현재 위치가 리스트 맨 끝 자리라면 초기로 돌아가도록 한다
    if current == len(x)-1:
        current = 0
    else: #아니라면 그냥 1 증가
        current +=1

    #만약 count가 삭제될 순번이 되었다면 삭제
    if count ==b:
        count =1
        result.append(x[current]+1)
        del x[current]
        current -=1 #삭제후 리스트 길이가 줄면서 범위를 넘게되는걸 방지하기 위해 -1
        continue
    count +=1

#도대체 왜 이렇게 출력하라고 했을까?
print('<', end='')
for i in range(len(result)-1):
    print(result[i], end='')
    print(', ',end='')
print(result[-1],end='')
print('>')

코딩이 조금 복잡해져서 주석으로 약간의 설명을 적었습니다.

 

사람이 삭제되어야 할 순간에는 결과값을 출력할 result리스트에 추가하였습니다.

 

코드의 주요 부분을 설명드리겠습니다. count는 삭제되는 번째의 수의 카운트입니다. 3번째 사람을 삭제시킨다고 하면 일단 3번째인 것을 알기위해 1부터 3까지 숫자를 세야할겁니다. 그 카운트입니다.

 

current는 현재 위치입니다. 7명의 사람이 있다고 치면, count와 함께 하나씩 증가하며 count가 삭제 위치에 도달했을때 현재 위치의 사람을 없애기 위해 존재하는 변수입니다.

다만 유의할 점이 있습니다. 현재위치가 리스트의 마지막일 경우 사람을 한명 삭제하면 리스트의 길이가 1 줄어듭니다. 사람을 삭제했을때 current 변수 값을 하나 줄이지 않으면 다음 계산때 리스트 밖을 벗어나게 되기 때문에 -1을 해줍니다.

current를 -1했을때 현재위치가 차이나는것은 while문을 시작하자마자 증가시켜주기 때문에 걱정하지 않으셔도 됩니다. 그리고 현재 위치가 리스트의 마지막 부분이라면 1을 증가시켜야 할 부분에서 리스트의 0번째 위치로 이동하도록 변경합니다. 원형리스트를 만들었다고 생각하면 됩니다.

 

while문을 통해 사람을 없애다가 사람이 한명밖에 안남았다면 그냥 그 사람을 결과 리스트인 result에 추가하고 반복문을 탈출합니다.

 

마지막으로 결과리스트를 출력할때 <3,1,4,....>의 모양을 갖추기위해 코드를 좀 작성해줍니다.