Menu

문서정보

배열 회전

n개의 원소를 가진 배열을 k번 만큼 오른쪽으로 회전하라.

예를 들어 n=7, k=3 이라면, 배열 [1,2,3,4,5,6,7]를 회전하면 [4,5,7,1,2,3,4]가 된>다.

Intermediate Array

package main

import (
    "fmt"
)

func main() {
    a := []int{1, 2, 3, 4, 5, 6, 7}
    Rotate(a, 3)
    fmt.Println(a)
}

// [1,2,3,4,5,6,7]
// [5,6,7,1,2,3,4]
func Rotate(a []int, k int) {
    if k > len(a) {
        k %= len(a)
    }
    result := make([]int, len(a))
    bound := len(a) - k
    j := 0
    for i := 0; i < k; i++ {
        result[i] = a[bound+i]
        j++
    }
    for i := 0; i < bound; i++ {
        result[j] = a[i]
        j++
    }
    copy(a, result)
}
		
원본 배열과 동일한 크기의 배열을 만들어서, 순환된 결과를 복사한다. 공간복잡도 O(N), 시간복잡도 O(N)이다.

Bubble Rotate

버블소트를 응용해서 공간 복잡도를 O(1)로 줄일 수 있다.
package main

import (
    "fmt"
)

func main() {
    a := []int{1, 2, 3, 4, 5, 6, 7}
    Rotate(a, 3)
    fmt.Println(a)
}

func Rotate(a []int, k int) {
    if k > len(a) {
        k %= len(a)
    }
    for i := 0; i < k; i++ {
        for j := len(a) - 1; j > 0; j-- {
            temp := a[j]
            a[j] = a[j-1]
            a[j-1] = temp
        }
    }
}
		
공간 복잡도는 O(1)이지만 시간 복잡도는 O(n*k)다. 예제의 경우 시간복잡도는 8(length) * 3 이 될 것이다.

거울 반전

반전(Reversal)을 이용해서 O(1) 공간, O(n) 시간으로 회전 할 수 있다. 현재 코딩 중...