[Ruby] Josephus 문제 (LinkedList 구현)

알고리즘 책을 읽다가 Linked List 의 예제로 Josephus 문제가 나왔다. 원형 테이블에 N명의 사람들이 있고, M 번째 원 밖으로 빼서 정렬시키는 문제다. Circular Linked List의 구현을 보여주려고 나온 문제인데 C언어 코드는 40줄 남짓 간단하다. 그래서 이걸 Ruby로 만들어도 간단하지 않을까 하고 일을 벌였다가 무려 두 배나 긴 코드를 만들어버렸다.

처음에는 Ruby의 배열을 이용해서 단순하게 만들어보려고 했는데, 어쩌다보니 배가 산으로 가서 Ruby에서 여기의 연결 리스트를 참고해서 새로 구현하고 말았다.

뼈 속까지 C 프로그래머라 OOP 개념이 없는 상태에서 클래스로 만든 건 좋은 경험인 듯 싶다. 클래스와 메서드를 어떻게 만드느냐에 따라 정말 루비스럽게 이쁜 코드도 나올 수 있을 것 같은데 당장은 이 정도에서 만족... 처음에는 TDD로 만들 생각이었는데, 연결 리스트의 객체를 단위테스트로 어떻게 확인해야 할 지도 잘 모르겠고, 뭉텅이로 코딩하다 보니까 TDD의 흔적은 없고 단위 테스트 조각만 조금 남았다. 하지만 실제로 구현하면서 단위 테스트의 도움은 많이 받았다. (코딩도장 부지러히 다니니까 눈에 보이게 달라진 점인 듯...)

코드를 새로 구현하면서 책에 나와있던 예제 코드도 좀 더 분명하게 이해하게 되었고, 배열과 연결 리스트에 대해서도 다시 한 번 생각하게 되었다.


#!/usr/bin/ruby
require "test/unit"

class LinkedList
  attr :t_node
  attr :s_node

  class Node
    attr :key
    attr_reader :next
    attr_writer :next

    def initialize(key)
      @key = key
      @next = nil
    end
  end

  def initialize
    @t_node = Node.new(1)
    @s_node = @t_node
  end

  def add(key)
    node = Node.new(key)
    node.next = nil
    @t_node.next = node
    @t_node = node
  end

  def end
    @t_node.next = @s_node
    @t_node = @s_node
  end

  def do_next
    @s_node = @t_node
    @t_node = @t_node.next
  end

  def do_delete
    if @s_node == @s_node.next
      return nil
    end

    @s_node.next = @t_node.next
    @t_node = @t_node.next
  end
end

def init_list(count)
  linked_list = LinkedList.new

  (2..count).each {| c | linked_list.add(c)}
  linked_list.end

  return linked_list
end

def get_list(list, jump)
  result = Array.new

  loop do
    (jump-1).times do
      list.do_next
    end
    result.push(list.t_node.key)
    if list.do_delete == nil
      break
    end
  end

  result
end

def josephus(n, m)
  return get_list(init_list(n), m)
end

class TestJosephus < Test::Unit::TestCase
  def test_make_list
    list = init_list(9)
    assert_equal [5, 1, 7, 4, 3, 6, 9, 2, 8], get_list(list, 5)
    assert_equal [5, 1, 7, 4, 3, 6, 9, 2, 8], josephus(9, 5)
  end
end