CodilityのCyclicRotationを競プロ未経験が解いてみた

前回に引き続き、Codilityを解いてみました。今回はArrayの章のCyclicRotationです。
CyclicRotationとは簡単に言うと、配列を輪に見立てた時に反時計周りにN要素分移動しなさいと言う問題です。例えば、[1, 5, 2, 8, 1, 4, 7]と言う配列を３回ローテーションすると[1, 4, 7, 1, 5, 2, 8]となります。

今回はこのCyclicRotationをPythonとJavaで組んで見ました。
いずれのコードも100%の判定を貰うことができました。しかし、さらに効率のいいやり方があるかもしれません。特にJavaはあまり慣れていないので自信はありませんでした。

アルゴリズム

今回はPythonとJavaで書きましたが、アルゴリズムは基本的に同一です。

与えられた配列の最後の要素を、先頭に移動する作業をK回繰り返すだけです。

Python

Pythonの配列の実態はリストであり、固定長ではなく要素の削除や追加が自由にできるので比較的簡単に実装することができました。

def solution(A, K):

    array = A

    # Aが空ならそのまま返す
    if array == []:
        return A
    # 最後の要素を先頭に移動する作業をK回行う
    for _ in range(K):
        cache = A[-1]
        array.pop(-1)
        array.insert(0, cache)

    return array

Java

基本的にはPythonと全く同じです。しかし、Javaの配列は固定長です。あらかじめ要素数を指定する必要があり、要素の削除や追加が行えません。
従って、事前にリストに変換する必要があります。また、返り値はint[]なのでリストを再び配列に変換しています。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[] solution(int[] A, int K) {

        // 与えられた配列Aが空だった場合はそのままAを返す
        if (A.length == 0) {
            return A;
        }

        // JavaのArrayをListに変換
        List<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < A.length; i++) {
            list.add(A[i]);
        }

        // Listの最後の要素を削除し先頭に追加する処理をK回繰り返す
        for  (int i = 0; i < K; i++) {
            int cache = list.get(list.size() - 1);
            list.remove(list.size() - 1);
            list.add(0, cache);
        }

        // ListをArrayに変換
        int[] array = new int[list.size()];

        for (int i = 0; i < list.size(); i++) {
            array[i] = list.get(i);
        }

        return array;
    }
}

まとめ

今回はJavaとPythonの２言語で実装しました。Pythonだけを書いていると[-1]で最後の要素が取れたりと普段は意識していませんでしたが、改めて便利さを実感しました。今後は次の章にも取り組みたいと思います。