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

연구실에서 실험 중에 facebook 에 링크가 하나 올라왔길래 풀어봅니다. ㅎㅎ 자꾸 딴 짓 하면 안되는데…;;

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

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

즉 shift(array, k)를 어떻게 구현하냐는 것인데요,

일반적으로 생각하기 쉬운 알고리즘은 2가지 정도가 있습니다.

첫째는 array를 하나 더 만들어서 각 element를 새로운 배열의 (element+k) MOD n 위치로 복사하는 방법이 있습니다. 가장 일반적인 방법이지만, 창의적이지는 않지요.

둘째는, 해답이라기 보다도 트릭이겠지만, 위의 (element_k) MOD n 을 함수처럼 제공하는 방법이 있습니다. 즉 shift(array, k, i)를 억세스하면 shift 된 array를 반환시키는 방법이죠. 하지만 이것은 문제에서 요구하는 방법은 아니니까 패스…

#!/usr/bin/ruby

# Reverse the array
def rev(a,s,e)
    for i in 0..(e-s-1)/2 do
        tmp=a[s+i]
        a[s+i]=a[e-i]
        a[e-i]=tmp
    end
end

# Shift the array with size of k with three reverses
def func(a,k)
    rev(a,0,a.length-1)
    rev(a,0,k-1)
    rev(a,k,a.length-1)
end

arr = Array.new
arr = [1, 2, 3, 4, 5, 6]

puts "Original = " + arr.inspect

func(arr,3)

puts "Shifted  = " + arr.inspect

    rev(a,0,a.length-1)

a = [6, 5, 4, 3, 2, 1]

    rev(a,0,k-1)

a = [4, 5, 6, 3, 2, 1]

    rev(a,k,a.length-1)

a = [4, 5, 6, 1, 2, 3]