자료구조 - 배열 문제 : 배열의 회전

연습문제 : 배열의 회전

 

정수들이 포함되어 있는 배열과, 숫자 k가 입력으로 주어짐. 이때 해당 배열을 k 만큼 회전 시켜봐.

예를 들어서, [1, 2, 3, 4, 5, 6, 7, 8, 9] 와 4가 입력으로 주어졌을 경우 [6,7,8,9,1,2,3,4,5] 를 반환하면 됨.

• k 는 배열의 길이 n 보다 작다고 가정.
• 다양한 방법으로 풀어 볼 수 있음.
• (추가) 공간 복잡도 O(1)으로 풀 수 있는 방법도 생각. 이때 주어진 함수 partialReverse를 활용해도 됨.

# 이 함수를 수정 해 주세요.
def rotateArray(nums, k):
    return nums

# 다음 함수는 추가적인 공간 사용 없이 배열의 일부를 뒤집어 주는 함수입니다.
# 예를 들어, nums = [1,2,3,4,5]
# partialReverse(nums, 1, 3)
# 을 실행 할 경우, nums = [1, 4, 3, 2, 5] 가 됩니다.
# 필요하다면 사용하세요.
def partialReverse(nums, start, end):
    for i in range(0, int((end-start)/2) + 1):
        temp = nums[start + i]
        nums[start+i] = nums[end - i]
        nums[end -i] = temp


def main():
    nums = [1,2,3,4,5]
    partialReverse(nums, 1, 3) # [1, 4, 3, 2, 5] 를 반환합니다.
    print(nums)
    print(rotateArray([1,2,3,4,5,6,7,8,9], 4)) # [6,7,8,9,1,2,3,4,5] 를 반환해야 합니다.
    

if __name__ == "__main__":
    main()

 

>>>

def rotateArray(nums, k):
    # [1, 2, 3, 4, 5, 6, 7, 8, 9] -> [6, 7, 8, 9, 1, 2, 3, 4, 5]
    # [1, 2, 3, 4, 5, 6] + [6, 7, 8, 9] -> [6, 7, 8, 9] + [1, 2, 3, 4, 5] 나눠서 뒤바꾼거
    # [1, 2, 3, 4, 5] = nums[:5]
    # [6, 7, 8, 9] = nums[5:]
    # result = nums[5:] + nums[:5]
    # 5 = len(nums) - k
    
    return nums[len(nums)-k:] + nums[:len(nums)-k]
    
    def main():
    nums = [1,2,3,4,5]
    print(nums)
    print(rotateArray([1,2,3,4,5,6,7,8,9], 4)) # [6,7,8,9,1,2,3,4,5] 를 반환
    

if __name__ == "__main__":
    main()
    
# 따로 메모리 공간을 필요로 하는 변수가 없고, 인자로 주어진 nums와 k만으로 코드가 완성되었으니까
# Big-O 공간복잡도 = O(1)

 

>>>

partialReverse 함수를 사용한다면,

def rotateArray(nums, k):
    partialReverse(nums,0,len(nums)-1)
    # 일단 이렇게 함수를 적용시키면 배열 전체를 회전시키는거니까 아예 뒤집혀

    #그리고 [9, 8, 7, 6]을 [6, 7, 8, 9]로 바꿔
    partialReverse(nums,0,k-1)
    
    # 이제 [5, 4, 3, 2, 1]을 [1, 2, 3, 4, 5]로 바꿔
    partialReverse(nums,k,len(nums)-1)
    return nums


# 다음 함수는 추가적인 공간 사용 없이 배열의 일부를 뒤집어 주는 함수
# 예를 들어, nums = [1,2,3,4,5]
# partialReverse(nums, 1, 3)
# 을 실행 할 경우, nums = [1, 4, 3, 2, 5]

def partialReverse(nums, start, end):
    for i in range(0, int((end-start)/2) + 1):
        temp = nums[start + i]
        nums[start+i] = nums[end - i]
        nums[end -i] = temp


def main():
    nums = [1,2,3,4,5]
    partialReverse(nums, 1, 3) # [1, 4, 3, 2, 5] 를 반환
    print(nums)
    print(rotateArray([1,2,3,4,5,6,7,8,9], 4)) # [6,7,8,9,1,2,3,4,5] 를 반환
    

if __name__ == "__main__":
    main()