[Arrays] CyclicRotation

알고리즘에 대한 태클 열렬히 환영합니다~

한 수 가르쳐주십쇼~~

Lesson 2 Arrays CyclicRotation

URL : https://codility.com/programmers/lessons/2-arrays/cyclic_rotation/

N개의 정수로 구성된 배열 A가 있습니다.

배열의 Rotation은 모든 원소가 오른쪽으로 한 칸 씩 이동하는 것을 말합니다.

배열의 맨 마지막 항목은 배열의 첫번째 항목으로 이동하구요.

예를 들어, 배열 A가 [3, 8, 9, 7, 6]으로 주어졌을 때, Rotation하게 되면 [6, 3, 8, 9, 7]이 됩니다.

이 문제의 목표는 배열 A를 K번 Rotation 하는 겁니다.

즉, 배열 A의 각 원소가 오른쪽으로 K만큼 움직인 배열을 만들면 됩니다.

아래와 같은 함수를 작성합니다 :

struct Results solution(int A[], int N, int K);

N개의 정수로 구성된 배열 A와 정수 K가 주어집니다.

그리고 이 함수는 K번 Rotation 된 배열 A를 반환합니다.

예를 들어 A=[3, 8, 9, 7, 6] 배열과 K = 3이 주어졌을 때, [9, 7, 6, 3, 8]을 반환합니다.

제약조건

- N과 K는 0~100사이의 정수입니다.

- 배열 A의 각 원소는 -1000~1000 범위를 갖습니다.

이 문제의 해답은 정확도만 있으면 됩니다.

퍼포먼스는 나중에 생각해 보시길 바랍니다.

C언어 100% 점수 획득 코드

void Rotate(int a[], int N) {

int temp, i;

temp = a[N-1];

for(i=N-1; i>0; i--) {

    a[i] = a[i-1];

}

a[0] = temp;

}

struct Results solution(int A[], int N, int K) {

struct Results result;

int i;

for(i=0; i<K; i++) {

Rotate(A, N);

}

result.A = A;

result.N = N;

return result;

}

K를 이용해서 오른쪽으로 shift 해야할 index를 계산해서 연산량을 줄일 수도 있겠지만

문제의 의도대로 정확도만을 집중한 소스코드 입니다.

Rotate함수에서는 배열의 맨 마지막 항목을 저장하고, 모든 배열의 원소를 오른쪽으로 한 칸 씩 shift 합니다.

shift가 완료된 후에는 저장했던 마지막 항목 값을 배열의 맨 첫자리에 대입해줍니다.

solution 함수에서는 K에 따라 Rotation함수를 반복호출하여

정확하게 K번 shift 된 배열을 결과로 반환합니다.

한 번에 K 씩 shift하려면 맨 뒤부터 K개의 원소를 따로 저장한 뒤,

나머지 원소들을 '원래 index + K'만큼 shift 해주고, 미리 저장한 K개 원소를 배열의 앞부분에 대입해 주면 됩니다.

이렇게 구현 할 경우, 배열 원소를 한 칸 씩 shift하는 기존 방법보다 대입연산량이 확 줄어들게 됩니다.

다만, index를 잘못 계산하여 Segmentation fault가 나는걸 주의하셔야 합니다.

모듈러 연산으로 범위를 제한하는 방법도 있을 수 있겠네요.