Codility - CyclicRotation 풀이

Lesson2. CyclicRotation

안녕하세요!

저번 시간에는 Lesson1. BinaryGap에 대해 풀이해봤습니다.

이번에는 Lesson2의 CyclicRotation을 2가지 방법으로 풀이해보려 합니다.

Question

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

CyclicRotation coding task - Learn to Code - Codility

정리하자면, 주어진 K 만큼 배열을 오른쪽으로 회전시키는 문제입니다.

 

주어진 배열이: [1, 2, 3, 4], K가 3과 같다면,

 

1. [4, 1, 2, 3]

2. [3, 4, 1, 2]

3. [2, 3, 4, 1]

 

가 되어, [2, 3, 4, 1]을 반환하면 됩니다!

Answer - 1 (Mutable)

첫 번째는 Mutable 한 풀이입니다.

자바스크립트의 Array 메서드 중 unshift()와 pop()을 이용하였습니다.

*unshift() 메서드는 새로운 요소를 배열의 맨 앞쪽에 추가, pop()은 배열의 마지막 요소를 제거함과 동시에 그 요소를 반환하는 역할을 합니다!

 

풀이 코드는 아래와 같습니다.

function solution(A, K) {
  if (!A.length) {
    return [];
  }

  for (let idx = 0; idx < K; idx++) {
    A.unshift(A.pop());
  }
  
  return A;
}

Answer - 2 (Immutable)

두 번째는 Immutable 한 방법입니다.

 

1. 주어진 배열과 길이가 같은 새로운 배열 만들기

2. 주어진 배열의 길이보다 작을 때까지 루프를 돌며, *새로운 배열의 인덱스에 기존 배열의 값 넣기

3. 새로운 배열 반환

 

*새로운 배열의 인덱스에 기존 배열의 값 넣기

=> newArr[(idx + K) % A.length] = A[idx];

 

Question 단계에서의 예제를 바탕으로 해당 코드를 풀이해보겠습니다.

주어진 배열 A는 [1, 2, 3, 4], K는 3이라고 했을 때, 결과는 [2, 3, 4, 1]이 나와야 합니다.

idx(인덱스)는 0부터 A의 길이보다 작을 때(3)까지 증가하게 됩니다.

 

idx가 0일 때

    - newArr[(0 + 3) % 4] = A[0]

    =>  newArr[3] = 1;

 

idx가 1일 때

    - newArr[(1 + 3) % 4] = A[1]

    => newArr[0] = 2;

 

idx가 2일 때

    - newArr[(2 + 3) % 4] = A [2]

    => newArr[1] = 3;

 

idx가 3일 때 (마지막)

    - newArr[(3 + 3) % 4] = A[3]

    => newArr[2] = 4;

 

즉, 새로운 배열 newArr는 결국 [2, 3, 4, 1]이 됩니다.

다른 예제들로 한 번 테스트해보셔도 좋을 듯합니다.

 

풀이 코드는 아래와 같습니다.

function solution(A, K) {
  const newArr = [];
  const arrLeng = A.length;
  
  if (!arrLeng) {
    return [];
  }
  
  for (let idx = 0; idx < arrLeng; idx++) {
    newArr[(idx + K) % arrLeng] = A[idx];
  }
  
  return newArr;
}

 

Comparison

두 방법 모두 결과는 동일하지만, 퍼포먼스 측면에서 비교해봤을 때 큰 차이점이 있습니다.

 

첫 번째 구현 방법 중, unshift() 메서드는 push() 메서드와 유사하게 보이지만 배열의 맨 앞쪽에 추가한다는 것이 가장 큰 차이이자 특징입니다.

기존 배열의 값들을 변화시키지 않고 맨 앞쪽에 값을 추가를 하려고 한다면, 기존 위치에 있던 요소들의 위치는 N이면 N + 1로, N2은 N2 + 1와 같이 이동될 수밖에 없습니다.

하지만 이는 매우 비효율적인 과정이기 때문에, 실제로는 메모리를 새로 할당하고, 새로운 요소를 추가 한 다음, 기존의 스택(OldStack)을 새로운 스택(NewStack)에 복사하는 작업들을 하게 됩니다. (= 항상 메모리를 재할당하고 데이터를 복사한다는 것)

 

아래의 퍼포먼스 그래프가 2차나 지수 함수와 같이 보이는 것이 그 이유이며,

console 객체의 time 및 timeEnd 메서드를 이용하여 같은 요소들이 담긴 배열에 대한 테스트를 해봤을 때 시간 차이가 명확하게 드러납니다.

 

push()와 unshift()의 퍼포먼스 그래프

 

The End

아직까진 퍼포먼스 부분을 크게 신경 쓰지 않아도 되지만, 계속 문제를 풀다 보면 되게 중요해질 것 같다는 느낌이 듭니다.

구현만 됐다고 좋아할 것이 아니라, 어떻게 하면 좀 더 좋은 퍼포먼스를 낼 수 있을지, 더욱 깔끔한 코드를 짤 수 있을지를 항상 염두에 두고 문제를 풀어야 할 것 같습니다..

다음에는 Lesson2. OddOccurrencesInArray에 대해 풀이해보려합니다.

봐주셔서 정말 감사합니다!

Reference

https://stackoverflow.com/questions/44031591/performance-of-array-push-vs-array-unshift?noredirect=1&lq=1