문제로 풀어보는 알고리즘 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를 반환시키는 방법이죠. 하지만 이것은 문제에서 요구하는 방법은 아니니까 패스…

스크립팅 언어를 사용하면 코딩량을 줄일 수 있는 다른 괜찮은 트릭이 나오겠지만, 문제에서 코딩량 보다는 O(n) 알고리즘을 어떻게 효율적으로 구현하느냐의 트릭을 요구하는 것 같아서 한 번 reverse 를 3번 구현해서 shift를 구현하는 방법을 사용해 보았습니다. 예전 고등학생 때 올림피아드 준비하면서 알아뒀던 알고리즘인데, 여기서 다시 볼 줄은 몰랐네요. ㅎㅎ

ruby 로 된 답을 한번 제시해봅니다.

#!/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()를 3번 이용해서 Shift 시키게 됩니다. rev()는 주어진 array의 주어진 범위 내에 있는 원소들의 위치를 반대 방향으로 만들어주는 함수입니다.

하나씩 뜯어보면

    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]

이 되어서 shift 연산을 완료하게 됩니다.

실제로 shift를 구현할 때 위 방법이 많이 쓰이는지는 모르겠군요. 메모리 가격이 중요했던 예전에는 array 하나로 해결할 수 있는 저런 알고리즘이 각광을 받았는데, 요즘은 뭐… 그냥 알아보기 쉬운 코드가 제일이 아닌가 싶습니다.

array가 정수라고 가정해서 덧셈을 이용한 swap을 하면 tmp 변수도 필요없이 swap 하는 트릭도 있습니다만, 대신 속도가 느려서 요즘은 쓸 일 없겠죠.