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

요새 심심할때 문제로 풀어보는 알고리즘책을 보고있습니다.

저같은 초보자한테 참 좋네요 : ) 

 

 

 

4년전에 알고리즘 트레이닝북으로 개발에 발을 들여놨던 기억이 나네요. 

정말 계란으로바위치기하듯이.......디버깅만 수천번한것같아요 ㅋㅋㅋㅋㅋㅋㅋㅋ (생각없이 무작정 코딩코딩~!! ㅎㅎ)

 

무튼 이번에 인사이트북에서 이벤트로  아래 이벤트를 열었습니다.

책보면서 생각 했던게 있어서 코딩시작.....;;

http://www.insightbook.co.kr/post/3814

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int data[] = {1, 2, 3, 4, 5, 6, 7, 8};

void right_rotate(int begin, int end, int k)
{
    int length = end-begin+1;
    int divide_into = length/2 + 1;
    int *temp = (int*) malloc(sizeof(int)*(divide_into));

    int *arr = data + begin;

    if (length < k)
        k = k % length;

    if ( divide_into <= k ) {
        memcpy(temp, arr, (length-k)*sizeof(int));
        memmove(arr, arr+(length-k), k*sizeof(int));
        memcpy(arr+k, temp, (length-k)*sizeof(int));
    } else if (divide_into > k ) {
        memcpy(temp, arr+(length-k), k*sizeof(int));
        memmove(arr+k, arr, (length-k)*sizeof(int));
        memcpy(arr, temp, k*sizeof(int));
    }
   free(temp);
}
int main(int argc, char* argv[])
{
    int i;

    for (i = 0; i < sizeof(data)/sizeof(int); i++)
        printf ("[%d]: %d\t", i, data[i]);
    puts("");

    right_rotate(2, 6, 2);

    for (i = 0; i < sizeof(data)/sizeof(int); i++)
        printf ("[%d]: %d\t", i, data[i]);
    puts("");
    return 0;
}

 

 

 

요새 ruby를 시작해서 ruby로 하면 어떻게 될까.....해서 봤더니....엄머....rotate라는 함수가 있네요. 

아래와 같이 짜봤습니다.

class Array
        def right_rotate (first, last, k)
                length = last - first
                k %= length if k > length

                tmp = self.slice!(first..last)
                tmp.rotate!(-k)
                idx = first
                tmp.each do
                |item|
                        self.insert(idx, item)
                        idx += 1
                end
        end
end

arr = [1, 2, 3, 4, 5, 6, 7, 8]

puts "before:\t"+arr.inspect

arr.right_rotate 2, 6, 1
puts "after:\t"+ arr.inspect

 

 

 

c는 범위에 반을 나눠서(divide_into) 옮기려고 하는크기에 따라서 다르게했습니다. 

사용하는 메모리를 조금이나마 아껴보고자;;; 

 

ruby는 slice로 범위만큼 도려내고, rotate한다음에 다시 insert. 간단합니다. 

이런 재미있는 이벤트를 기획하신 인사이트북. 감사합니다~!!