문제로 풀어보는 알고리즘 0.3 생각해보기 풀이 1주차 Etc

인사이트 이벤트 : http://www.insightbook.co.kr/post/3814

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

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

-----------------------------------------------------------------------------------------------------------


여러가지 방법으로 풀 수 있는데, 그 중 가장 쉽고 기본적인 방법으로 풀었다.
정해진 길이의 배열을 복사한 후, 인덱스의 최종 위치를 modulo로 구해서 때려박는다.

이미 코멘트들에 많이 박혀있는 대로 이 방법은 추가적인 메모리를 필요로 하므로 조금 더 얍삽하게 변형된
알고리즘을 통해 메모리를 그대로 두고 시프팅 하는 방법도 있을 듯 하다.

void rotate(int* arr, int s, int t, int k)
{
int *tmp = new int[t-s+1];
memcpy(tmp, arr+s, sizeof(int)*(t-s+1));

for(int i = 0; i <= t-s; ++i)
arr[ i+s ] = tmp[ (i+k*(t-s))%(t-s+1) ];

delete [] tmp;
}


덧글

댓글 입력 영역