백준-1158-조세퍼스문제

조세퍼스는 간단하면서도 인터뷰시에 자주 물어볼만한 문제다.

나는 deque를 이용해서 풀었으나, linkedList로 구현하는 방법과 일반 리스트의 인덱스를 계산하는 방법도 있다.

문제

조세퍼스 문제

풀이

1. 문제조건 해석

   조세퍼스 문제

2. 알고리즘

   • deque를 사용하는 방법
   • linkedList 방법
   • 배열 인덱스를 계산하는 방법

3. 코드

   • deque

    from collections import deque
    n, k = [int(x) for x in input().split()]
   
    queue = deque([int(x) for x in range(1,n+1)])
    answer = '<'
    while queue:
        for it in range(k):
            queue.rotate(-1)
        else:
            answer += str(queue.pop())+', '
        print
    else:
        answer = answer[:-2]+'>'
    print(answer)
   

   • 인덱스 계산하는 방법.

    def solution(ipt):
    n, m = map(int, ipt.split())
    arr = list(range(1, n+1))
    index = m - 1
    result = []
    while len(arr) > 0:
        index %= len(arr)
        result.append(arr.pop(index))
        index += m - 1
    print("<" + ", ".join(map(str, result)) + ">")