[백준 알고리즘/Python3] 1158 요세푸스 문제

문제이해

리스트 하나를 만들어 두고 원형태를 생각해서 k의 값에 따라 증가하면서 리스트를 pop()하는 형태로 만들었습니다. k의 값이 초과하면 남아있는 리스트 개수의 나머지로 계산했습니다.

 

 

 

코드

n, k = map(int, input().split())

li = [i for i in range(1,n+1)]

point = li.index(k)
numerical = []

#li가 빌 때까지 한다.
while(len(li)):
    #해당 값을 꺼낸다.
    result = li.pop(point)
    numerical.append(str(result))

    #li가 비어있다면 탈출
    if(len(li) == 0):
        break
    else:
        #k-1은 인덱스가 0부터 시작하기 때문
        point = (point + (k-1)) % len(li)


print("<",", ".join(numerical),">", sep='')

• 출력할 때 < > 으로 감싸야하고, 빈공간을 없에기 위해 sep=''을 처리했습니다.
• while문을 들어가는 순간에는 li가 살아있어서 point를 계산하는 연산이 되지만 pop()을 먼저해서 li가 텅 비게됩니다. 그렇기 때문에 li가 빈다면 while문을 탈출합니다.
• 왜 k-1만큼 움직이냐면 리스트의 인덱스는 0부터 시작하기 때문입니다. 우리가 생각한 k값은 1부터 시작한것이죠
• join연산을 할 때 파라미터는 str형태로 해야합니다.

 

 

다른게 본 코드

큐를 이용해서도 풀 수 있었습니다. 큐의 형태로 시작합니다.

• 0에서 k-1까지를 큐의 뒤쪽보냅니다. (offer)
• k번째가 되면 해당 값을 출력합니다. (poll)
• Queue에 값이 1개 남아있을 때 까지 반복합니다.

코드보러가기