C#으로 배열을 k번 회전하는 방법 – 3단계 뒤집기 알고리즘

배열 회전 문제란?

배열과 숫자 k가 주어졌을 때, 배열을 k번 회전하는 것이 이 문제의 목표입니다. 예를 들어 k가 3으로 주어지면 배열을 세 번 회전해야 합니다.

가장 효율적인 해결 방법은 reverse(뒤집기) 함수를 활용하는 것입니다. 이 함수는 배열과 시작 인덱스(start), 끝 인덱스(end)를 매개변수로 받아 해당 구간의 요소들을 서로 교환하며 뒤집습니다.

해결 접근 방식

총 세 번의 뒤집기를 통해 원하는 결과를 얻을 수 있습니다.

• 1단계: 전체 배열(0부터 배열 끝까지)을 대상으로 reverse 메서드를 호출합니다.

• 2단계: 처음(0)부터 k-1 인덱스까지 reverse 메서드를 호출합니다.

• 3단계: k 인덱스부터 배열 끝까지 reverse 메서드를 호출합니다.

이 세 단계를 거치면 배열이 정확히 k만큼 오른쪽으로 회전됩니다. 추가 배열 없이 제자리(in-place)에서 처리되므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

예제 코드

using System;
namespace ConsoleApplication{
    public class Arrays{
        public void ReverseArrayKTimes(int[] arr, int k){
            Reverse(arr, 0, arr.Length - 1);
            Reverse(arr, 0, k - 1);
            Reverse(arr, k, arr.Length - 1);
        }
        private void Reverse(int[] arr, int start, int end){
            while (start < end){
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
                start++;
                end--;
            }
        }
    }
    class Program{
        static void Main(string[] args){
            Arrays a = new Arrays();
            int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
            a.ReverseArrayKTimes(arr, 3);
            for (int i = 0; i < arr.Length; i++){
                Console.WriteLine(arr[i]);
            }
            Console.ReadLine();
        }
    }
}

동작 과정 살펴보기

입력 배열 { 9, 8, 7, 6, 5, 4, 3, 2, 1 }에 k = 3을 적용하면 다음과 같이 진행됩니다.

1. 전체 뒤집기 → { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

2. 앞부분(k-1까지) 뒤집기 → { 3, 2, 1, 4, 5, 6, 7, 8, 9 }

3. 나머지 부분(k부터 끝까지) 뒤집기 → { 3, 2, 1, 9, 8, 7, 6, 5, 4 }

출력 결과

3 2 1 9 8 7 6 5 4