Menu

문서정보

배열 뒤 바꾸기

n개의 원소를 가진 배열을 뒤집는다. n=7 때, 배열 [1,2,3,4,5,6,7]를 [7,6,5,4,3,2,1]로 회전하기 위한 몇 개의 방법이 있는가.

Intermediate Array

package main

import (
    "fmt"
)

func main() {
    r := rotate([]int{1, 2, 3, 4, 5, 6, 7, 8, 9})
    fmt.Println(r)
}

func rotate(a []int) []int {
    result := make([]int, len(a))
    for i := 0; i < len(a); i++ {
        result[i] = a[len(a)-(i+1)]
    }
    return result
}
		
아마도 가장 간단하게 생각 할 수 있는 방법일 것이다. 원본 배열과 같은 크기의 배열 을 만들고, 원본 배열의 맨 뒤에서 부터 순환하면서 값을 복사한다. O(n) 공간과 O(n) 시간이 필요하다.

O(1) Reverse

O(1) 공간을 사용하는 방법을 찾아보자.
package main

import (
    "fmt"
)

func main() {
    val := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    rotate(val)
    fmt.Println(val)
}

func rotate(a []int) {
    var temp int
    for i := 0; i < (len(a) / 2); i++ {
        temp = a[i]
        a[i] = a[len(a)-(i+1)]
        a[len(a)-(i+1)] = temp
    }
}
		
O(1)이며 공간 복잡도는 O(n)이다.