Cyclic Rotation

문제 설명

배열이 주어지고, 정수 K가 주어질 때, 배열을 오른쪽으로 K번 회전시킨 결과를 반환하는 문제입니다. 배열에서 회전이란, 배열의 마지막 요소가 배열의 첫 번째 요소로 이동하고 나머지 요소는 한 칸씩 뒤로 밀리는 것을 의미합니다.

예를 들어:

• 배열 [3, 8, 9, 7, 6]이 있을 때, K = 3이면 배열은 [9, 7, 6, 3, 8]로 변합니다.

해결 방법

알고리즘 설명

1. 주어진 배열 A와 회전 횟수 K에 대해, 배열의 크기를 N이라고 할 때, 사실 K가 배열의 크기 N보다 크면 K % N 만큼만 회전하면 됩니다. 예를 들어, K = N이면 배열이 한 바퀴 돌아 원래 상태로 돌아옵니다.
2. 배열을 K % N 만큼 오른쪽으로 회전시키면, 결과는 배열을 두 부분으로 나누어 합치는 방식으로 구현할 수 있습니다.
3. 배열을 회전시키는 방식은 다음과 같습니다:
   • A.slice(N - K % N) 부분을 배열의 맨 앞에 놓고,
   • A.slice(0, N - K % N) 부분을 뒤에 놓습니다.

코드 구현

function solution(A: number[], K: number): number[] {
  const length = A.length

  // 배열이 비어 있을 경우 그대로 반환
  if (length === 0) return A

  const rotation = K % length

  // 회전 횟수가 0일 경우 원래 배열 그대로 반환
  if (rotation === 0) return A

  const splitIndex = length - rotation

  // 배열을 두 부분으로 나누어 합침
  return [...A.slice(splitIndex), ...A.slice(0, splitIndex)]
}

코드 설명

1. 빈 배열 처리: 배열 A가 비어 있을 경우 회전을 수행할 필요가 없으므로 바로 반환합니다.
2. 회전 횟수 최적화: K가 배열의 크기보다 클 수 있기 때문에, K % length를 사용하여 실제로 필요한 회전 횟수를 계산합니다.
3. 배열 분할 및 재조합: 배열을 slice를 사용하여 두 부분으로 나누고, 이를 합쳐서 새로운 배열을 만듭니다.

시간 복잡도

• 배열을 slice를 사용하여 두 부분으로 나누는 데 O(N) 시간이 걸립니다.
• 따라서 이 알고리즘의 시간 복잡도는 **O(N)**입니다.

예시

예시 1

입력:

;(A = [3, 8, 9, 7, 6]), (K = 3)

출력:

;[9, 7, 6, 3, 8]

예시 2

입력:

;(A = [0, 0, 0]), (K = 4)

출력:

;[0, 0, 0]

예시 3

입력:

;(A = [1, 2, 3, 4]), (K = 2)

출력:

;[3, 4, 1, 2]

시간 복잡도

• O(N) — slice로 배열을 나누는 비용