LeetCode: Rotate Array

문제설명

• 정수형 배열이 주어졌을 때, 배열의 오른쪽으로 k 만큼의 항목 까지만 회전하라

문제풀이

1. 하나씩 꺼내어 앞으로 추가하기

• 배열을 linked list로 구현했을 때 적합하다.

// 1. Pop and Push one by one
func rotate_popAndPush(_ nums: inout [Int], _ k: Int) {
    for _ in 0..<k {
        if let last = nums.popLast() {
            nums.insert(last, at: 0)
        }
    }
}

 

2. 뒤집기

• k를 기준으로 왼쪽 섹션과 오른쪽 섹션으로 나눈다.
• 배열의 왼쪽 섹션과 오른쪽 섹션을 나누어 뒤집는다.

// 2. Reverse
func rotate_reverse(_ nums: inout [Int], _ k: Int) {
    guard nums.count > 1 else { return }
    let k2 = k%nums.count
    if k2 == 0 { return }
    // reverse left section
    let leftSectionLastIndex = nums.count-k2-1

    reverse(&nums, startIdx: 0, endIdx: leftSectionLastIndex)
    // reverse right section
    let rightSectionStartIndex = (leftSectionLastIndex+1) % nums.count
    reverse(&nums, startIdx: rightSectionStartIndex, endIdx: nums.count-1)

    nums.reverse()
}

func reverse(_ nums: inout [Int], startIdx: Int, endIdx: Int) {
    for i in 0...(endIdx-startIdx)/2 {
        nums.swapAt(startIdx+i, endIdx-i)
    }
}


// TEST

var arr1 = [1,2,3,4,5,6,7]
rotate_reverse(&arr1, 1) // [7,1,2,3,4,5,6]
print(arr1)

arr1 = [1,2,3,4,5,6,7]
rotate_reverse(&arr1, 3) // [5,6,7,1,2,3,4]
print(arr1)

var arr2 = [1,2]
rotate_reverse(&arr2, 2) // [1,2]
print(arr2)

arr2 = [1,2]
rotate_reverse(&arr2, 1) // [2,1]
print(arr2)