CLOSE

Recommanded Free YOUTUBE Lecture: <% selectedImage %>

### 배열 회전

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) 시간으로 회전 할 수 있다. 현재 코딩 중...