CyclicRotation

/Codility

문제 해석

요약

주어진 배열 A를 K만큼 회전하는 것이다. 회전이라는 것은 배열의 숫자가 오른쪽으로 이동하는 것이고, 마지막 요소는 맨 앞으로 위치한다. N과 K는 0-100 범위 정수이고, A의 각 요소는 -1000~1000 내의 정수이다.

전문

🇰🇷 번역

정수 N개가 포함된 배열 A이 주어진다. 배열을 회전한다는 의미는 각 요소가 하나의 인덱스만큼 오른쪽으로 이동하고, 배열의 마지막 요소는 가장 앞쪽으로 이동하는 것을 의미한다. 예를 들어, 배열 A = [3, 8, 9, 7, 6]의 회전은 [6, 3, 8, 9, 7]이다.(요소가 오른쪽으로 하나의 인덱스 만큼 이동하고, 6은 처음 자리로 이동된다.)

배열 A를 K번 회전하는 것이 목표이다; 즉, A의 각 요소는 K번 오른쪽으로 이동해야한다.

함수를 작성하시오:

function solution(A, K);

정수 N개를 포함하는 배열 A와 정수 K가 주어지면, K번 회전한 배열 A를 리턴한다.

주어진 것이 아래와 같다면,

A = [3, 8, 9, 7, 6]
K = 3

함수는 [9, 7, 6, 3, 8]을 반환해야한다. 3번 회전은 다음처럼 만든다:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

다른 예로 아래와 같이 주어진다면,

A = [0, 0, 0]
K = 1

함수는 [0, 0, 0]를 반환한다.

또 다른 예로 다음과 같이 주어진다면,

A = [1, 2, 3, 4]
K = 4

함수는 [1, 2, 3, 4]을 반환한다.

다음처럼 가정한다:

  • N과 K는 [0..100] 범위 내의 정수이다;
  • 배열 A의 각 요소는 [−1,000..1,000] 범위 내의 정수이다.

솔루션은 정확성에 집중해라. 솔루션의 성능을 평가의 기준으로 하지 않을 것이다.

🇺🇸 원문

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

function solution(A, K);

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given

A = [3, 8, 9, 7, 6]
K = 3
the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]
For another example, given

A = [0, 0, 0]
K = 1
the function should return [0, 0, 0]

Given

A = [1, 2, 3, 4] [3, 4, 1, 2]
K = 4
the function should return [1, 2, 3, 4]

Assume that:

  • N and K are integers within the range [0..100];
  • each element of array A is an integer within the range [−1,000..1,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

🤔 문제 해결 방법 구상

  1. K값을 배열 A의 길이와 관련하여 정리.

    • K값은 배열 A 요소의 인덱스를 이동시키는데, 이것은 결국 회전이다. 그래서 K가 배열 A의 길이가 되면, 회전의 결과는 배열 A 그대로이다.
    • K를 배열 A의 길이로 나눈 나머지값과 결과가 같다.
  2. 배열의 길이를 넘어가는 인덱스를 정리.

    • 인덱스에 K를 더하면 이동하는 인덱스가 되는데, 범위를 넘어가는 인덱스들은 맨 앞으로 오게 된다.
    • 리턴할 배열에서 인덱스 = (기존 인덱스 + 위에서 계산한 k값) % 배열 A의 길이
  3. 새로운 배열에 정리된 인덱스로 할당.

코드 구현

function solution(A, K) {
  let k = K % A.length;
  if (k === 0) return A;

  let result = [];
  for (let i = 0; i < A.length; i++) {
    let newIndex = (i + k) % (A.length);
    result[newIndex] = K[i];
  }
  return result;
}

결과 분석

Task Score: 100%
Correctness: 100%
Performance: 100%

for문을 순회하기 때문에, 배열의 길이에 따라 복잡도가 증가한다. 그러므로 시간복잡도는 O(n)이다. 마찬가지로 result의 길이가 배열의 길이만큼 공간이 필요하므로, 공간복잡도도 O(n)이다.

마무리

복잡해 보일 수 있지만, 인덱스 이동의 결과가 반복되는 점을 이용하면 복잡하지 않게 풀 수 있었다.
주어진 배열을 순회하고 인덱스로 접근, 새로운 배열을 만들고 배열을 수정하는 배열을 다루는 기본적인 연습을 할 수 있는 문제다.

Reference & Learn More

MDN Array

Tags
Comments