Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
‘문제로 풀어보는 알고리즘 0.3 생각해보기 풀이’

이벤트 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

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

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;
}
}
package org.fupfin.insight.event1;
public interface ArrayRotator<T> {
public T[] rotateRight(T[] target, int step);
}
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);
}
}
package org.fupfin.insight.event1;
public class BlockCopyArrayRotatorTest extends RotatorTest {
@Override
public <T> ArrayRotator<T> getRotator() {
return new BlockCopyArrayRotator<T>();
}
}
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;
}
}
package org.fupfin.insight.event1;
public class IterativeCopyArrayRotatorTest extends RotatorTest {
@Override
public <T> ArrayRotator<T> getRotator() {
return new IterativeCopyArrayRotator<T>();
}
}
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);
}
}
@fupfin

This comment has been minimized.

Copy link
Owner Author

@fupfin fupfin commented Sep 7, 2012

인사이트에서 진행하는 이벤트 첫주 첫번째 문제 풀이입니다.

dfdf
df
dfd
fd
f

@fupfin

This comment has been minimized.

Copy link
Owner Author

@fupfin fupfin commented Sep 7, 2012

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment