본문 바로가기
코딩 공부

Leetcode Rotate Array 파이썬 시도

by 카우보이연구소 2022. 1. 13.

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

Array, rotate?

문제: Rotate Array
등급: Medium

내용: "Given an array, rotate the array to the right by k steps, where k is non-negative."

주어진 배열에서, 배열을 k 스탭만큼 돌려라. (k는 >0)

 

예시)

Input: nums = [1,2,3,4,5,6,7,8] k = 2

output:  [7,8,1,2,3,4,5,6]

 

<코드>

class Solution(object):
    def rotate(self, nums, k):
        if k == 0:
            return nums
        
        # so that !o(n)
        cut = k % len(nums)
        
        # k steps = [-cut:] is moved in front of the array
        a = nums[-cut:]
        # cut the array that is going to be moved
        del nums[-cut:]
        # insert in front of the array
        nums[0:0] = a
        
        return nums

<(내가 이해한) 논리>

우선, k = 0이면 rotate을 안해도 된다. 그래서, 그대로의 배열을 돌려준다.

 

k 가 0이 아니라면, rotate을 해줘야한다. 하지만, 계속 k 횟수만큼 rotate하는 것은 너무나도 많은 시간이 걸린다. 1번, 2번이면 상관이 없겠다만은, 만약에 10000번 정도 한다면? 그리고 배열이 1000이라면?

 

그래서, 만약에 k가 len(nums), 배열의 길이보다 길다면 계속 몇바퀴를 제자리로 돌려놓을 것이다. 그래서, cut = k % len(nums)을 넣었다.

 

그 후는 간단하다. 뒤에서 cut 만큼 자르고, 앞에 넣고, 그 배열을 돌려주었다.

 

<오류, 힘들었던 점>

처음에 계속 뺑뱅이 돌려서 시간초과가 계속 나왔다. k가 크면 배열을 제자리로 계속 돌린다는 점을 생각하지 못하였다.

 

<총평>

어려웠다.

def rotate(self, nums, k):
        n = len(nums)
        # cut 대신 k
        k = k % n
        # 한문장 통합
        nums[:] = nums[n-k:] + nums[:n-k]

Discussion에 위의 solution이 있는데, 내가 한 것보다 훨씬 간단하고, 문장도 줄이고, 굳이 새로운 variable를 만들지 않아 좋은 듯 하다.

 

Happy coding!

댓글1