1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# rotate.coffee
arr = [1..8]
s = 2
t = 6

rotate = (k) ->
    len = t-s+1
    k = k % len
    __rotate k, s, len

__rotate = (k, i, len) ->
    if len is 0 then return
    temp = arr[i]
    next = (i-s+k) % (t-s+1) + s
    __rotate(k, next, len-1)
    arr[next] = temp

rotate 1
console.log arr # [ 1, 2, 7, 3, 4, 5, 6, 8 ]

CoffeeScript를 튜토리얼만 살짝 읽고 언젠가 써봐야지하면서 쓸 일이 없었는데 겸사겸사 이번 기회에 써봤다. 분명 타자는 더 적어진거 같은데 손에 안익어서 문서를 보면서 코딩해서 그런지 시간은 더 늘어난 기분. 튜토리얼말고 제대로 된 문서를 정독하고 나서 나중에 다시 도전해봐야겠다.

배열 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 생각해보기 풀이’라는 문장이 들어가야 합니다. (저희 블로그에도 트랙백을 걸어주세요.) (주의: 이 코딩 인터뷰는 인사이트 입사와는 무관합니다. ㅡㅁㅡ /)

문제에 대해서 접근하자면, 간단하게 생각해서 마지막 숫자를 저장해두고 그 자리에 올 숫자를 마지막 숫자의 자리에 옮기고, 이걸 (t-s+1-1)번 (실제 옮겨지는 아이템의 수 -1) 옮기고 나서 처음에 저장해두었던 숫자를 k만큼 이동하면 된다. 그런데 모듈러 연산이라는게 역산하기 어려운고로 제일 쉬운 방법은 옮길 아이템의 수 (t-s+1) 만큼 공간을 만들고 값을 복사한 뒤에 그림에 나온 것처럼 t-s+1번 이동하는 방법이 제일 간단하고 명확했다. 그런데 몇줄 안나오는 코드로는 재미가 없어서 지금 있는 공간에서 해결할 수 있는 방법을 찾다가 요즘 읽고 있는 그 책에서 자꾸 재귀적인 알고리즘을 강요하듯 반복해서 재귀적으로만 풀이하니 전염이 되었나 한번 재귀적으로 풀어보고 싶었다.

단순하게 생각해서 arr만 가지고 풀기를 시도해보면, [2]에 있는 3을 [3]으로 옮기려한다. 그럼 [3]에 있는 4가 사라지니 3을 일단 메모리에게 들고 있으라고 한 뒤에 4부터 옮기고 3을 [3]에 넣으면 될 것이다. 이런 식으로 들어가야할 자리가 비어있지 않으면 잠시 메모리에 놓고 다음꺼부터 옮기다가 자리가 비어있으면 (t-s+1 번만큼 호출된 후에) 그냥 이동만 하고 아까 메모리에 놔두었던 것들을 원하는 자리에 차례대로 넣으면 된다. 문제는 이런 경우에 자료의 크기 자체에 더해서 call stack만큼의 비용을 추가로 부담하게 되니, 메모리 사용이 4*k에서 (4+@)*k로 늘어나게 되니 오히려 더 비효율적이 될 수도 있고, heap보다 stack이 조금 더 빠르니 비슷할 수도 있다. 원래의 의도는 그냥 재귀적으로 도전해보는 것이었으니 그 이상은 여기까지 생각하고 잘 돌아가는 것에서 만족하도록 하자.