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

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

 

전체 코드

N, K = map(int,input().split())
list1 = []
result = []

for i in range(N):
    list1.append(i+1)

k_ = K-1
while(len(list1) != 0):
    
    if k_ < len(list1):
        result.append(list1[k_])
        list1.pop(k_)
        k_ += K -1
    else :
        k_ %= len(list1)
        result.append(list1[k_])
        list1.pop(k_)
        k_ += K - 1

result_str = "<" + ", ".join(str(i) for i in result) + ">"
print(result_str)

 

풀이 설명

• 입력받은 N만큼 1~N의 배열을 만들어준다.

for i in range(N):

    list1.append(i+1)

• 위의 리스트 길이가 0이 될 때까지 반복한다 

while(len(list1) != 0)

• 인덱스는 0부터 시작하므로 입력받은 K에서 -1 한 값을 인덱스로 사용해준다.
• 지우고 싶은 인덱스가 리스트 길이보다 작다면 지우는 값을 result 리스트에 저장하고 pop해준다.(리스트에서 제거)  그리고 인덱스는 k-1만큼 +해준다. (그 다음번째 요소를 삭제해야하므로)

if k_ < len(list1):

        result.append(list1[k_])

        list1.pop(k_)

        k_ += K -1

• 만약 지우고 싶은 인덱스 번호가 리스트 길이보다 크다면 인덱스 % 리스트 길이를 해주면 원하는 인덱스 번호를 얻을 수 있다. 그리고 지우는 값을 result 리스트에 저장하고 해당 요소를 제거해준다. 그리고 인덱스는 k-1만큼 +해준다.

else :

        k_ %= len(list1)

        result.append(list1[k_])

        list1.pop(k_)

        k_ += K - 1

• 출력 형식이 <1, 2, 3, 4> 이므로 join을 이용하여 요소들 사이에 ','를 넣어준다 . 그러나 join은 문자열 리스트나 문자열이 포함된 리스트에서만 가능하다. (즉, 숫자 리스트에서는 불가능) 그러므로 새로운 문자열을 만들어준다. 

result_str = "<" + ", ".join(str(i) for i in result) + ">"

",".joijn(str(i) for i in result) //숫자 리스트를 문자열 리스트로 바꾸고 각 요소 사이에 ","를 넣어주었다.

 

지우고싶은 인덱스가 리스트 길이를 넘어갈 때 원하는 인덱스를 구하는 곳에서 애를 먹었다.
k_ %= len(list1)