C 프로그램에서 배열의 왼쪽 회전 결과를 O(n) 시간·O(1) 공간으로 출력하기

크기가 n인 배열과 하나 이상의 정수 값 k가 주어졌을 때, 주어진 인덱스 k를 기준으로 배열을 왼쪽으로 회전한 결과를 출력해야 합니다.

예를 들어 배열을 인덱스 k부터 회전하면 다음과 같은 형태가 됩니다.

예시

입력: arr[] = {1, 2, 3, 4, 5}
    K1 = 1
    K2 = 3
    K3 = 6
출력:
    2 3 4 5 1
    4 5 1 2 3
    2 3 4 5 1

핵심 아이디어

이 문제의 핵심은 모듈로(%) 연산입니다. 배열을 실제로 회전시키지 않고, 회전된 것처럼 보이는 순서로 요소에 접근하는 방식입니다. 먼저 k % n을 계산해 실제 필요한 회전 횟수를 구하고, 이후 (cal + i) % n을 인덱스로 사용해 배열을 한 번 순회하며 출력합니다. 덕분에 추가 메모리 없이 O(n) 시간 안에 처리할 수 있습니다.

알고리즘

시작
1단계 -> 함수 void leftRotate(int arr[], int n, int k) 선언
    int cal = k % n 선언
    int i = 0부터 i < n까지 i++ 반복
        arr[(cal + i) % n] 출력
    반복 종료
2단계 -> main() 함수에서
    배열 a[] = {1, 2, 3, 4} 선언
    int size = sizeof(a) / sizeof(a[0]) 선언
    int k = 1 선언 후 leftRotate(a, size, k) 호출
    k = 2로 설정 후 leftRotate(a, size, k) 호출
    k = 3으로 설정 후 leftRotate(a, size, k) 호출
종료

구현 예제

#include <bits/stdc++.h>
using namespace std;
void leftRotate(int arr[], int n, int k){
    int cal = k % n;
    for (int i = 0; i < n; i++)
        cout << (arr[(cal + i) % n]) << " ";
    cout << "\n";
}
int main(){
    int a[] = { 1,2,3,4};
    int size = sizeof(a) / sizeof(a[0]);
    int k = 1;
    leftRotate(a, size, k);
    k = 2;
    leftRotate(a, size, k);
    k = 3;
    leftRotate(a, size, k);
    return 0;
}

출력 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

2 3 4 1
3 4 1 2
4 1 2 3

복잡도 분석

배열을 정확히 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 회전된 배열을 저장하기 위한 별도의 임시 배열이나 버퍼를 사용하지 않으므로 공간 복잡도는 O(1)입니다. k가 배열 크기 n보다 큰 경우에도 k % n으로 나머지를 구해 처리하기 때문에 어떤 k 값이 들어와도 올바른 결과를 얻을 수 있습니다.