인사이트 에서 재미있는 행사를 하길래 도전해보았다.


문제는 다음과 같다.


배열 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 생각해보기 풀이’라는 문장이 들어가야 합니다. (저희 블로그에도 트랙백을 걸어주세요.)

(주의: 이 코딩 인터뷰는 인사이트 입사와는 무관합니다. ㅡㅁㅡ /)


구체적인 조건에 대한 언급은 없지만 별도의 메모리는 사용하지 않는게 좋겠다는 생각이 들었다. 


그리고 1만큼 오른쪽으로 이동시키는 과정을 k번 반복해서는 안된다고 하니 O(n)으로 풀기를 원하는구나.


해결전략은 코드와 같다.


#include <stdio.h>

const int MAX_ELEM = 10;

void rotate(int *array, int s, int t, int k)
{
	int range = (t - s + 1);
	int idx = s, cycle = s;
	int insert, save;

	if (k % range == 0) return ;
	if (k > range) k %= range;

	insert = save = array[s];

	for(int i = 0; i < range; i++) 
	{
		insert = save;

		int nextIdx = idx + k;

		// invalid range check
		if (nextIdx > t) {
			nextIdx = (nextIdx % (t+1)) + s;
		}

		save = array[nextIdx];
		array[nextIdx] = insert;

		idx = nextIdx;

		// avoid cycle 
		if (idx == cycle) {
			idx++; cycle++;
			save = array[idx];
		}
	}
}

int main()
{
	int array[MAX_ELEM];

	// make test set
	for(int i = 1; i <= MAX_ELEM; i++) {
		array[i-1] = i;
	}

	rotate(array, 0, 6, 3);

	// print result
	for(int i = 0; i < MAX_ELEM; i++)
		printf("%d ", array[i]);
	printf("\n");

	return 0;
}


간단히 설명하면, 저장될 곳에 있는 값을 변수에 저장해둬서 덮어쓰더라도 값을 보존시켜가는 방식이다.


그 다음 이동은 지금 덮어씌워진 위치에서 시작한다. 현재 덮어쓴 자리에 있던 값은 저장해두었기 때문에 


다음 위치에 저장할 값을 보존할 수 있다. 마찬가지로 다음 위치에 있는 값을 save에 저장하고, 


기존에 있던 값(insert)으로 덮어쓰면 된다. 


이 과정을 범위만큼 반복하면 별도 메모리 필요없이 풀 수 있다.


Posted by DevMoon

댓글을 달아 주세요

  1. DevMoon 2012.08.30 03:07 신고  댓글주소  수정/삭제  댓글쓰기

    코드에 순환하는 경우를 고려하지 못해서 보완... avoid cycle 이 부분..

  2. 망고스파게티 2012.09.12 23:50 신고  댓글주소  수정/삭제  댓글쓰기

    save한 인덱스에서 다시 시작해버리는 거군요. 모든 경우에 다 일정하게 이동하기 때문에 누락되는 인덱스도 없고, 이 방법이 딱 알맞네요! 최고입니다!!