Scala로 풀어본 개미수열(읽고 말하기 수열)

개미수열은 꽤 유명하다. 

1

11 (1이 1개)

12 (1이 2개)

1121 (1이 1개, 2가 1개)...

이런 식으로 무한히 이어져 가는 수열인데 몇가지 방면에서 만들어볼만한 수열이라고 생각한다.

Run-length encoding이라는 것과도 비슷하다.

1. 간단한 방법

우리가 푸는 방법 그대로를 구현한다면 어떨까? 

이전 단계의 수열을 입력받아 각 수를 세게 하는 방법이다. 

수열을 리스트로 입력받는다고 했을 때, 리스트의 앞부분부터 숫자가 같으면 count를 증가시키고 다르면 숫자와 개수를 정답으로 붙이면 된다.

/**
  * @param lst 현재 단계의 수열
  * @param numb 현재 세고 있는 수
  * @param count numb의 개수
  * @return 다음 단계의 수열
  */
def antLst1(lst: List[Int], numb: Int, count: Int = 1): List[Int] = lst match{
  case h::t =>
    if(numb == h) // h가 세고있는 수라면 count를 증가시켜 재귀호출한다.
      antLst1(t, numb, count + 1) 
    else // 아니라면 numb와 count를 결과로 가지고 h부터 다시 세기 시작한다.
      numb :: count :: antLst1(t, h) 
  case Nil => numb :: count :: Nil
}

2. 이 수열이 길어지면

이 수열은 기하급수적으로 늘어난다. 

늘어나지 않는 22같은 특이한 경우도 있지만 (물론 줄어들기도 한다) 대부분의 수는 다음 수열의 길이를 더 길게 만든다. 

메모리 크기를 따로 설정하지 않은 내 컴퓨터에서는 위의 메소드를 반복해서 호출하면 31~32번째 수열에서 StackOverFlow가 발생한다. 

긴 수열의 값을 구하기 위해 메소드가 계속해서 재귀호출되기 때문일 것이다. 

위 함수는 꼬리재귀를 사용해 반복문으로 바꿀 수 있다.

/**
  *  antLst1 함수와 같지만 중간 결과를 담는 
  *  리스트를 파라미터로 가지고 꼬리재귀로 구현했다.
  * 
  * @param lst 현재 단계의 수열
  * @param numb 현재 세고 있는 수
  * @param count numb의 개수
  * @param result 다음 단계 수열의 중간 결과
  * @return 다음 단계의 수열
  */
@tailrec
def antLst2(lst: List[Int], numb: Int, count: Int, result: List[Int] = Nil): List[Int] = lst match{
  case h::t =>
    if(numb == h) antLst2(t, numb, count + 1, result)
    else antLst2(t, h, 1, numb :: count :: result)
  case Nil => numb :: count :: result
}

반복문으로 변환된 이 메소드는 이제 StackOverFlow가 발생하지 않고 계속 진행된다.

3. 100번째 수열의 x번째 값을 구하려면?

100번째 수열의 x번째 값을 구하기 위해 99번째 수열을 끝가지 구해야 할까? 그럴 필요가 없다는 것은 누구나 안다.

이런 형태로 계산이 요구된다.

그렇다면 100번째 수열의 x번째 값을 구하려면 99번째 수열의 몇 번째 값까지 계산해야 할까?

300번째? 400번째? 대충 넣어서 답이 나올 수 있을지 몰라도 정확히 필요한만큼 계산했는지는 장담할 수 없다.

이 때 지연 콜렉션인 Stream을 사용하면 요구된 값을 구하기 위해 필요한 만큼만 계산하게 되므로 효율적으로 결과를 얻어낼 수 있다.

def antLst3(lst: Stream[Int], numb: Int, count: Int = 1): Stream[Int] = lst match {
  case h #:: t =>
    if (h == numb) antLst3(t, numb, count + 1)
    else numb #:: count #:: antLst3(t, h)
  case Stream.Empty => numb #:: count #:: Stream.empty[Int]
}

def lookAndSayRec(lst: Stream[Int] = Stream(1)): Stream[Stream[Int]] = {
  val result = antLst3(lst.tail, lst.head)
  result #:: lookAndSayRec(result)
}