‘문제로 풀어보는 알고리즘 0.3 생각해보기 풀이’

_READMEME.md

이벤트 1주차 첫 번째 문제를 풀어 봅니다.

문제

배열 arr[]과 위치 s, t가 있을 때

• arr[s], arr[s+1], … , arr[t-1]을 오른쪽으로 한 칸씩 이동하고,
• arr[t]는 arr[s]로 복사하는 것을 ’1만큼 오른쪽으로 회전시켰다’고 한다.

예를 들어 길이가 8인 배열에서 s=2, t=6이면 다음 그림처럼 바뀐다.

길이가 n인 배열의 위치는 0, 1, 2, … , n-1이다.

###문제

k를 인자로 받아서 k만큼 오른쪽으로 회전시키는 함수를 작성하라.

단, 1만큼 오른쪽으로 이동시키는 과정을 k번 반복해서는 안 된다.

###조건

1. 작성하는 언어에는 제한이 없습니다.
2. 답안으로 작성하신 글 제목에는 ‘문제로 풀어보는 알고리즘 0.3 생각해보기 풀이’라는 문장이 들어가야 합니다. (저희 블로그에도 트랙백을 걸어주세요.)

풀이

여러가지 방법이 떠올랐지만 두 가지만 구현했습니다.

###BlockCopyArrayRotator

배열의 첫 위치가 이동할 위치를 계산한 수 블럭 카피를 해서 새 배열을 만든다.

###IterativeCopyArrayRotator

배열을 순차적으로 하나씩 새 위치로 복사한다.

AbstractArrayRotator.java

package org.fupfin.insight.event1;

import java.lang.reflect.Array;

public abstract class AbstractArrayRotator<T> implements ArrayRotator<T>{

    @Override
    public T[] rotateRight(T[] source, int step) {
        if(isValidArguments(source, step))
            throw new IllegalArgumentException("step value have to be not negative number : " + step);
    
        if(isThereNoNeedToWork(source, step)) return source;
    
        @SuppressWarnings("unchecked")
        T[] result = (T[]) Array.newInstance(source[0].getClass(), source.length);
        int start = step % source.length;

        doRotattion(source, step, result, start);
        
        return result;
    }

    protected abstract void doRotattion(T[] source, int step, T[] result, int start);

    private boolean isValidArguments(T[] source, int step) {
        return step < 0;
    }

    private boolean isThereNoNeedToWork(T[] target, int step) {
        return target == null || target.length == 0 || step == 0;
    }

}

ArrayRotator.java

package org.fupfin.insight.event1;

public interface ArrayRotator<T> {
    public T[] rotateRight(T[] target, int step);
}

BlockCopyArrayRotator.java

package org.fupfin.insight.event1;

public class BlockCopyArrayRotator<T> extends AbstractArrayRotator<T> {

    @Override
    protected void doRotattion(T[] source, int step, T[] result, int start) {
        System.arraycopy(source, 0, result, start, source.length - start);
        System.arraycopy(source, source.length - start, result, 0, start);
    }
}

BlockCopyArrayRotatorTest.java

package org.fupfin.insight.event1;

public class BlockCopyArrayRotatorTest extends RotatorTest {

    @Override
    public <T> ArrayRotator<T> getRotator() {
        return new BlockCopyArrayRotator<T>();
    }
}

IterativeCopyArrayRotator.java

package org.fupfin.insight.event1;


public class IterativeCopyArrayRotator<T> extends AbstractArrayRotator<T> {

    protected void doRotattion(T[] source, int step, T[] result, int start) {
        for(T e: source)
            result[start ++ % source.length] = e;
    }
}

IterativeCopyArrayRotatorTest.java

package org.fupfin.insight.event1;

public class IterativeCopyArrayRotatorTest extends RotatorTest {

    @Override
    public <T> ArrayRotator<T> getRotator() {
        return new IterativeCopyArrayRotator<T>();
    }
}

RotatorTest.java

package org.fupfin.insight.event1;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public abstract class RotatorTest {

    public RotatorTest() {
        super();
    }

    public abstract <T> ArrayRotator<T> getRotator();

    @Test
    public void 한칸회전() {
        ArrayRotator<Integer> rotator = getRotator();
        Integer[] testArray = {0, 1, 2, 3};
        Integer[] result = rotator.rotateRight(testArray, 1);

        assertArrayEquals(new Integer[]{3,  0, 1, 2}, result);
    }

    @Test
    public void 두칸회전() {
        ArrayRotator<Integer> rotator = getRotator();
        Integer[] testArray = {0, 1, 2, 3, 4};
        Integer[] result = rotator.rotateRight(testArray, 2);

        assertArrayEquals(new Integer[]{3, 4, 0, 1, 2}, result);
    }

    @Test
    public void 한바퀴회전() {
        ArrayRotator<Integer> rotator = getRotator();
        Integer[] testArray = {0, 1, 2, 3, 4};
        Integer[] result = rotator.rotateRight(testArray, testArray.length);

        assertArrayEquals(testArray, result);
    }

    @Test
    public void n_minus_1회전() {
        ArrayRotator<Integer> rotator = getRotator();
        Integer[] testArray = {0, 1, 2, 3, 4};
        Integer[] result = rotator.rotateRight(testArray, testArray.length-1);

        assertArrayEquals(new Integer[]{1, 2, 3, 4, 0}, result);
    }
    
    @Test
    public void 문자열회전() {
        ArrayRotator<String> rotator = getRotator();
        String[] testArray = {"a", "b", "c", "뿡"};
        String[] result = rotator.rotateRight(testArray, 1);

        assertArrayEquals(new String[]{"뿡", "a", "b", "c"}, result);
    }
}

으엑! 댓글을 수정할 수가 없...;;;