[알고리즘]Arrays: Left Rotation

문제 링크

https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem?h_r=profile

풀이

이번 문제는 나름 간단했다. 주어진 a 배열을 d 횟수만큼 왼쪽으로 회전시키는 문제인데, 0 인덱스는 맨 오른쪽으로 돌아가는 원리였다.

배열을 회전한다는 것은 한 칸씩 이동하다가 배열의 크기만큼 회전을 하게 되면 결국 기존 배열이 그대로 유지가 된다. 그렇기 때문에 굳이 한바퀴 도는 걸 계산하지 않고 보통 나머지 연산으로 몇 번 이동을 해야하는지를 구하게 되는데, 이 문제에서도 기본적으로 d가 integer값이라고 적혀있었고 a 배열의 크기를 몰랐기 때문에, d>a.length일 가능성도 생각하여 d를 a.length로 나머지 연산을 하여 순수하게 a가 움직여야하는 횟수를 계산했다.

그 다음에는 실제로 한칸씩 배열을 이동 시키면 된다. 그런데 혹시 a배열이 꽤 길고 b가 a.length-1 이런식으로 제공이 되면 꽤나 시간이 오래 걸리게 될 것이다. 때문에 해결할 수 있는 방법을 구상해보았는데

1. a.length/2를 기준으로 b가 클 시 왼쪽이 아닌 오른쪽으로 a.length-b만큼 이동

   ⇒최대 횟수가 절반이 되버리니 횟수는 꽤 줄겠지만 그래도 integer최대값을 생각하면 꽤 큰 숫자이다.

2. 배열을 b만큼 왼쪽으로 이동시키면 [0]~[b-1]까지의 값이 a 배열의 오른쪽으로 간다는 것을 의미한다. 그러므로 한 번에 0~b-1까지를 splice를 이용해서 자른 뒤 잘린 a 배열 뒤에 붙이면 굳이 한칸씩 이동하지 않아도 된다.

위의 두가지 방법 중 2번을 사용해서 문제를 풀게 되었다. splice의 경우 잘린 배열이 반환되고 절단이 이루어진 배열은 실제 배열에 반영이 되므로 어렵지 않게 구현할 수 있었다.

코드

function rotLeft(a, d) {
    // Write your code here
    const rotCnt = d % a.length;
    const remain = a.splice(0, rotCnt);
    return [...a, ...remain]; 
}