리스트 회전에 대한 알고리즘

안녕하세요.

 

리스트를 k만큼 회전시키는 것에 대한 알고리즘은 무궁무진하게 많을 것라고 생각합니다.

 

저는 그냥 제가 학교에서 배운 내용에 대해 복습하고 생각해 볼 겸 게시글로 남겨봅니다.

 

 

전제

n만큼의 길이를 가진 리스트를 k칸만큼 회전시켜라.

 

방법

 

① 0 < k < n일 경우

 

index_value의 자리를 index_value + k - n 이 식을 통해 해결 할 수 있습니다.

def rotatelist(n: list, k: int):
    result = [None] * len(n) # 자리를 게산한 리스트를 넣을 빈리스트 생성
    for i in range(len(n)): # n의 길이만큼 반복을 돌며 각 리스트의 값의 자리를 찾음
        if i + k < len(n): # i + k가 n의 길이 보다 작을 경우를 위한 조건문
            result[i + k] = n[i]
        else:
            result[(i + k) - len(n)] = n[i]
    return result

n = [1,2,3,4,5,6]
print(rotatelist(n, 5))

 

 

② k가 n을 훨씬 상회하는 경우

def rotatelist(var_list: list, k: int):
    n = len(var_list)
    res = [None] * n
    for i in range(n):
        res[(i + k) % n] = var_list[i]
    return res

n = [1,2,3,4,5,6]
print(rotatelist(n, 8))

(i + k) mod n 이 회전 후의 index 값이라는 규칙(?)을 이용한 코드입니다.

 

 

③ 추가 리스트를 사용하지 않고 반복문으로 푸는 경우(k가 n을 훨씬 상회해도 가능)

def rotatelist(var_list: list, k: int):
    for i in range(k):
        n = len(var_list) - 1
        while n > 0:
            print(var_list)
            var_list[n], var_list[n - 1] = var_list[n - 1], var_list[n]
            n -= 1
    return var_list

n = [1, 2, 3, 4, 5, 6]
print(rotatelist(n, 5))

 

 

 

현재 알고 있는 것은 이 세가지입니다.

 

이것 말고도 파이썬의 collections 모듈을 이용해서 푸는 방법도 있지만, 아직 collections 모듈에 대해서도 미숙하고

 

배운게 전무하기 때문에 기회가 되면 소개하겠습니다.