[C/C++] 배열 shift 구현

[C/C++] 배열 shift 구현

• 간혹 알고리즘 문제를 풀다보면 배열에서 쉬프트 연산이 필요할 때가 있다.

• 이 경우 배열 뒤집기를 활용하여 간단히 해결할 수 있다.

arr = [1, 2, 3, 4, 5]
​
arr을 왼쪽으로 2칸 Shift 연산을 진행한다면?
arr = [3, 4, 5, 1, 2]
​
이 결과가 나와야 한다.
​
​
1. 앞에서 부터 2번째 원소까지를 뒤집자.
arr = [2, 1, 3, 4, 5]
​
2. 2번째 이후 원소 부터 끝까지 뒤집자.
arr = [2, 1, 5, 4, 3]
​
3. 전체 배열을 뒤집는다.
arr = [3, 4, 5, 1, 2]
​
이를 응용하면 오른쪽 Shift도 가능하다.

ShiftRight, ShiftLeft

void reverse(int arr[], int start, int end) {
    int temp;
    end = end - 1;
    while (start < end) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}
​
void shiftRight(int arr[], int d, int n) {
    reverse(arr, 0, n - d);
    reverse(arr, n - d, n);
    reverse(arr, 0, n);
}
​
void shiftLeft(int arr[], int d, int n) {
    reverse(arr, 0, d);
    reverse(arr, d, n);
    reverse(arr, 0, n);
}

main

void print(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}
​
int main() {
​
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    
    shiftRight(arr, 3, 10);
    print(arr, 10);
​
    shiftLeft(arr, 2, 10);
    print(arr, 10);
​
    return 0;
}

• 출력 결과는 다음과 같다.

• 8 9 10 1 2 3 4 5 6 7 : 오른쪽으로 3칸 Shift

• 10 1 2 3 4 5 6 7 8 9 : 다시 왼쪽으로 2칸 Shift