최후의 생존자

최후의 생존자

알고리듬 책에 나온 문제이다. 1번 부터 n번까지 n명의 사람이 있을 때 한명은 살고 그 다음 사람은 죽는 방법으로 생존자를 결정할 때 최후까지 남는 사람은 누구인가를 알아낸다.

예를 들어 5명이 있다면 1번은 살고 2번이 죽고 3번은 살고 4번이 죽고 5번은 살고 1번이 죽고 3번은 살고 5번이 죽고 나면 3번이 최후의 생존자가 된다.

1. 1, 2, 3, 4, 5
2. 1, 3, 4, 5
3. 1, 3, 5
4. 3, 5
5. 3

기본 프로그램은 C로 짜 보았다.

#include 
#include 
#include 

// 인자 크기 n의 정수 배열의 s부터 시작해서 0이 아닌 첫번째 항목을 찾는다
int searchSurvivor(int *ms, int s, int n) {
  if (s >= n) s = 0;
  while (*(ms + s) == 0) {
    s++;
    if (s == n) s = 0;
  }
  return s;
}

// 인자 n 크기의 members 정수 배열을 할당받은 후 1로 초기화 하고
// searchSurvivor 함수로 배열에서 생존자를 찾고 한번 더 함수로
// 사망자를 찾는 방식으로 구현했다.
int last(int n) {
  int i = 0, sur, *members;

  members = (int *)malloc(sizeof(int)*n);
  for (i=0; i<n; i++)
    *(members + i) = 1;

  sur = n;
  i = 0;
  while (sur != i) {    // 마지막은 생존자와 사망자가 같은 경우, 즉 유일한 생존자
    sur = searchSurvivor(members, i, n);
    // printf("생존자 %d를 찾았습니다.\n", sur+1);
    i = searchSurvivor(members, sur+1, n);
    *(members+i) = 0;
    // printf("%d가 사망했습니다.\n", i+1);
    i = searchSurvivor(members, i+1, n);
  }
  free(members);
  return sur;
}

int main(void) {
  struct timeval start, end;

  gettimeofday(&start, NULL);
  printf("%d가 살았습니다.\n", last(1000000)+1);
  gettimeofday(&end, NULL);

  long long run = end.tv_sec * 1000 + end.tv_usec - start.tv_sec * 1000 - start.tv_usec ;
  printf("총 실행시간은 %lld 밀리초입니다.\n", run);
  return 0;
}

functional programming으로 어떻게 구현할 수 있을까 고민하다 Set으로 구현했다. 1부터 n까지의 정수들로 이루어진 정수형 Set에서 생존자와 사망자를 찾아 사망자는 그 Set에서 제거한다. 한번에 한명의 사망자가 발생하므로 n-1번 실행하면 마지막 생존자가 남을 것이다.

def lastSurvivor(n:Int):Int = {
  // 크기 n의 정수형 Set s에서 from 부터 시작해서 존재하는 정수를 찾는다
  def circleFind(s:Set[Int], from:Int):Int =
    (from to n).find(s.contains(_)).orElse((1 to from).find(s.contains(_))).get
  // 1부터 n까지의 정수형 Set과 처음 생존자 1부터 시작해서 n-1번 사망자를 찾는다
  (1 until n).foldLeft(((1 to n).toSet, 1))({
    case ((st:Set[Int], sv:Int), _) =>
      /* val survivor = circleFind(st, sv)
      println(s"$survivor 가 살았습니다.")
      val dead = circleFind(st, survivor+1)
      println(s"$dead 가 죽었습니다.") */
      val dead = circleFind(st, circleFind(st, sv)+1)
      (st - dead, dead+1)
  })._1.head  // 답은 마지막 남은 Set에 유일한 값(head)
}

val start = System.currentTimeMillis
println(lastSurvivor(1000000))
val end = System.currentTimeMillis
println(s"${end-start} 밀리초가 걸렸습니다.")

컴파일에는 scala가 훨씬 시간이 걸렸지만 실행시간만 따져보면 의외로 scala가 조금 더 빨랐다. Set을 사용하는 것과 배열을 일일이 찾는 것의 차이가 아닐까. 혹은 멍청한 C 프로그램보다 잘 만든 라이브러리를 사용하는 Java나 Scala가 낫다.