Search Results for '스칼라 개미수열 scala look-and-say'

1 POSTS

  1. 2010.08.25 Scala '읽고 말하기 수열' 실습 (2)

Scala '읽고 말하기 수열' 실습

Posted 2010.08.25 01:44
 스칼라 스터디 멤버가 읽고 말하기 수열(개미수열)을 실습 퀴즈로 출제했는데, 짧고 재밌는 예제인 듯 하여 공유합니다. 당연한 말이지만, 푸는 방법은 여러 가지가 존재하므로 참고만 하심 되겠습니다.
 
 개미 수열이라고도 알려진 '읽고 말하기(look-and-say) 수열'은, 나열된 숫자를 "숫자 x가 y개"와 같은 식으로 읽으면 수열이 완성됩니다. 예를 들어 [1,1,2] 를 주어진 형식에 맞게 읽으면  숫자 1이 2개, 숫자 2가 1개이지요. 이를 수열로 나타낸 [1,2,2,1]이 개미 수열입니다.

 저는 다음과 같이 작성하였습니다.
// co-ons operator (~:)
// ex) List(1,1,1,2,3) == 1 ~: List(2,3)
object ~: {
  def unapply(list:List[Int]):Option[(Int, List[Int])] = {
    list match {
      case Nil => None;
      case x::xs => Some((x, xs.dropWhile( _ == x )));
    }
  }
}
 
 
object AntSeq {
  def lookAndSay(list:List[Int]):List[Int] = {
    list match {
      case Nil => Nil;
      case x~:xs => x::(list.size-xs.size)::lookAndSay(xs)     //co-ons
    }
  }
}

 우선 정의한 ~: 를 살펴볼 필요가 있습니다. 개미 수열의 단위는 반복되는 특정수의 묶음 입니다. 예를 들어 List(1,1,1,2,2,3)을 놓고 보면, 개미수열을 만들기 위해서는 List(1,1,1), List(2,2), List(3)과 같이 나누어 각 수를 셈할 필요가 있습니다. (적어도 제 머리는 그렇게 수열을 해석하는 것 같습니다.)

 이렇게 "기준 묶음을 뽑아내어 개수를 읽고, 나머지는 같은 요령으로(재귀적으로)처리한다."는 것이 핵심입니다. 기준 묶음과 나머지로 분리하기 위해 리스트를 다뤄본 사람[각주:1]이라면 지겹게 봤을 :: (cons)와 유사한 기호의 ~:를 이름을 살짝 바꾸어(co-ons)라고 정의했습니다.

List(1,1,1,2,2,3) = 1~:List(2,2,3) = 1~:2~:3

 눈으로 보니 co-ons의 정의가 더 간단합니다. 이를 패턴 매칭에 활용하여 개미 수열을 읽으려고 했습니다. 실제로 해당 역할을 하는 단 한 줄(17번째 줄)이 문제 풀이의 핵심이네요.수행 결과는 다음과 같습니다.
scala> import AntSeq._
import AntSeq._
 
scala> lookAndSay(List(1,1,1,2,2,3))
res0: List[Int] = List(1, 3, 2, 2, 3, 1)

 패턴매칭을 잘 활용하면, 자신이 가진 생각을 간단한 기호나 패턴으로 만들고 추상화할 수 있습니다. 그리고 함수형 스타일로 프로그래밍하는데 익숙해지면 문제 해결이 좀 더 빨라집니다. 제 경우 함수형 프로그래밍에 그렇게 익숙한 편도 아닌데, co-ons연산자를 도출하는 과정까지 포함해서 문제 푸는데 걸린 시간은 그렇게 길지 않았습니다. "제 머리가 생각하는 방법과 실제 프로그래밍의 간극이 가까웠기 때문"이라 생각합니다. 만일 for나 중간의 각종 변수를 정의하는 등 imperative style로 풀었다면, (적어도 저의 경우엔) 훨씬 오래 걸렸을 듯합니다. 

 scala가 가진 표현력과 함수형 프로그래밍 스타일[각주:2]의 문제 해결 능력을 맛볼 수 있는 좋은 예제였습니다. 출제해 준 스터디 멤버에게 감사!
  1. lisp 방언이나 hakell 등을 배워본 경험이 있다면 cons가 익숙할 겁니다. 심지어 lisp은 문법 트리조차 cons를 기반으로 표현되는데, 이는 http://en.wikipedia.org/wiki/Homoiconicity를 참고합니다. [본문으로]
  2. 참고로 scala는 functional style과 impertative style을 모두 지원하는 hybrid 언어입니다. [본문으로]
저작자 표시 비영리 변경 금지
신고

티스토리 툴바