본문 바로가기

hello world/algorithm

오늘의 알고리즘: Rotate Array (189. LeetCode)

leetcode.com/problems/rotate-array/

 

Rotate Array - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

 

 

여전히 원래 배열에서 조작해야 되는 문제인데

간단하게 생각하다보니 메모리도 많이 쓰고, 시간도 오래걸리네.

 

런타임이 빠른 애들은 상대적으로 for문이 너무 많이 돌고...

 

func rotate(nums []int, k int)  {
    sol2(nums, k)
}

// time: O(n), space: O(n)
func sol1(nums []int, k int) {
    pos := len(nums) - (k % len(nums))
    for i, n := range append(nums[pos:len(nums)], nums[0:pos]...) {
        nums[i] = n
    }
}

// time: O(n), space: O(1)
func sol2(nums []int, k int) {
    if len(nums) == 0 || k == 0 {
        return
    }
    
    next := nums[0] // todo
    swap := 0
    cur := 0
    done := 0
    
    for done < len(nums) {
        done++

        dest := (cur + k) % len(nums)
        //fmt.Println(cur, dest, next)

        swap = nums[dest]
        nums[dest] = next
        
        unit := k
        if (len(nums) - k < unit && len(nums) - k > 0) {
            unit = len(nums) - k
        }
        if len(nums) % unit == 0 && done % (len(nums) / unit) == 0 {
            dest = (dest + 1) % len(nums)
            swap = nums[dest]
        }

        cur = dest
        next = swap
    }
}

 

JS로 하면 좀 더 간결하게 짤 수 있을거 같은데

고랭 함수를 좀 더 봐야겠다.