Lesson 2. Arrays - CyclicRotation

1. 문제

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).
The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.
Write a function:
vector<int> solution(vector<int> &A, int K);
that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given
A = [3, 8, 9, 7, 6] K = 3
the function should return [9, 7, 6, 3, 8]. Three rotations were made:
[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

For another example, given
A = [0, 0, 0] K = 1
the function should return [0, 0, 0]

Given
A = [1, 2, 3, 4] K = 4
the function should return [1, 2, 3, 4]

Assume that:
N and K are integers within the range [0..100];
each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

주어진 vector A의 요소를 K만큼 이동시키는 문제. ( A[i + K] = A[i],  i = 0, 1, 2 ... N-1 )

만약 A의 크기를 벗어나면 0번째로 돌아가서 이동시키면 된다.

 

2. 풀이 전략

이동 거리는 K 값을 그대로 사용하지 않고, 나머지 연산자로 정제해서 사용한다.

왜냐하면 K값이 아무리 크더라도, 결국 A.size() 안에서 돌아야 하기 때문이다.

 

3. 주의사항

N and K are integers within the range [0..100];

N(vector<int> A의 크기)과 K가 0일 때 예외처리가 필요하다.

 

4. 코드 (C++)

vector<int> solution(vector<int> &A, int K) {
    
    // 예외처리
    if(A.empty()) return A;
    if(K == 0) return A;

    //이동해야할 거리
    size_t move_distance = K % A.size();
    
    vector<int> result(A.size(), 0);
    for(size_t i = 0; i < A.size(); i++)
    {
        size_t idx = i + move_distance; //이동해야할 곳
        if( idx < A.size() )
        {
            result[idx] = A[i];
        }
        else
        {
            result[idx - A.size()] = A[i];
        }
    }

    return result;
}