[Algorithm] 해커랭크 - Arrays: Left Rotation

https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem

주어진 배열을 Left Rotation 시키는 아주 기본적인 문제이다.

예전 모 기업의 코드테스트 중 이 오퍼레이션이 나왔었는데, 첫문제로 주어져 긴장이 안풀려서 그런지 동작은 되는 엉망진창인 코드를 제출한 기억이 있다. 그래서 포스트로 작성해 본다.

vector<int> array_left_rotation(vector<int> a, int n, int k) {
    int tmpValue = 0;
    int moveValue = a[0];
    int dindex = 0;
    vector<int> returnarray(n);
    for(int i = 0; i < n; i++)
    {
        dindex = i-k;
        if(dindex < 0)
            dindex = dindex+n;
        returnarray[dindex] = a[i];
    }
    return returnarray;
}

모듈러 연산을 활용해 간단하게 목적지 index를 구할 수 있지만, C언어(또는 C++)의 경우 음수에 모듈러 연산을 취하면 음수가 나와버리기 때문에 if문을 이용해 음수일 경우 배열 길이 N을 더해 목적 index 값을 구하게 했다.

처음에는 a -> b, b -> c, c -> d 순으로 순차적으로 이동을 시키면 될 것이라 생각해 코드를 제출했지만 2개 테스트 케이스가 fail이 나왔다. 확인해 보니 배열길이가 20, 10 left rotate를 할 경우 똑같은 위치만 반복하는 결과가 나오는것을 깨닫고 새 array에 복사하는 방법을 썼다.

메모리 제한이 있어 배열을 하나 더 사용 못 하는 경우 순차적으로 한번씩 left rotate 연산을 수행해 해결하는 방법이 있다. 이 경우 시간적 측면에서 비용 소모가 심하다.

* Array에서 이 연산의 구현은 변수를 일일히 이동시켜 줘야 하나 List 같은 경우 한 Rotation 당 Head를 Tail에 붙혀주기만 하면 되므로 좀더 빠른 연산이 가능하다.