Scala-99-Problems 솔루션 : P08 ~ P13

이미지 출처 : Pixabay

이번 글에서는 리스트 내 중복 및 Run-length encoding에 대한 문제인 P08 ~ P13 에 대한 솔루션을 포스팅하고자 합니다.

마찬가지로 리스트의 head::tail 특성을 활용하여 재귀적으로 작성하였습니다.

---

P08. 리스트 내에 연속하여 중복된 원소들을 제거하는 함수를 작성하시오. 만약 리스트가 반복되는 원소를 가지고 있다면 단일 원소로 대체되어야 하며, 원소들의 순서는 변경되어서는 안된다.

P08. Eliminate consecutive duplicates of list elements. If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.

 

문제가 조금 복잡해보이지만 주어진 리스트와 반환해야 할 리스트를 확인해 보면 어떤 함수 작성을 요구하는지 명확해집니다.

주어진 리스트는 List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)이며, 반환해야 할 리스트는 List('a, 'b, 'c, 'a, 'd, 'e)입니다.

즉, head::tail 특성을 활용한다면 head와 tail.head가 같은 경우, head를 제거하고 tail만을 붙이면 됩니다.

(이 때, tail이 Nil인지 꼭 확인해 주어야 합니다.)

중복 제거

소스 코드는 다음과 같습니다 :

  def compress[T](list:List[T]):List[T] = list match {
    case Nil => Nil
    case head :: Nil => head :: Nil
    case head :: tail => if (head == tail.head) compress(tail) else head :: compress(tail)
  }

---

P09. 리스트 내에 연속하여 중복된 원소들을 리스트 안의 리스트, 즉 하위 리스트(sublist)로 압축하는 함수를 작성하시오. 이 떄, 연속하여 중복된 리스트의 원소들은 종류별로 분리하여 순서대로 하위 리스트(sublist)로 압축되어야 한다.

P09. Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.

 

이번 문제도 복잡해 보이지만 P08과 같이 입력과 출력을 보면 단순하게 접근할 수 있습니다. 이번에는 중복된 원소들을 삭제하지 않고 종류별로 분리하여 하위 리스트로 압축하여야 합니다.

주어진 입력은 List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)이고, 출력은 List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))가 되어야 합니다.

저는 이 문제를 해결하기 위해 주어진 리스트에 map 함수를 사용하여 원소들을 모조리 List[T] 형태로 변환한 다음, P08과 같이 head와 tail.head를 비교하는 방법을 택했습니다. 함수 내부에 정의한 innerPack[T] 함수에서 head.last가 tail.head와 같다면 head에 tail.head를 추가하고, tail에서 head를 제외한 tail.tail을 다시 innerPack[T]로 넘겨주었습니다.

그림으로 정리하면 다음과 같습니다 : 

innerPack[T] 함수를 사용한 방법

소스 코드는 다음과 같습니다 : 

  def pack[T](list:List[T]):List[List[T]] = {
    def innerPack[T](nlist:List[List[T]]):List[List[T]] = nlist match {
      case Nil => Nil
      case head :: Nil => head :: Nil
      case head :: tail => if (head.last == tail.head.last) innerPack((head :+ tail.head.last) :: tail.drop(1)) else head :: innerPack(tail)
    }
    innerPack(list map(i => List(i)))
  }

만일 pack을 List[List[T]]가 아닌 List[Any]를 리턴하는 함수로 작성한다면 다음과 같은 솔루션도 가능합니다 : 

  def packAny(list:List[Any]):List[Any] = list match {
    case Nil => Nil
    case head :: Nil => head :: Nil
    case (head:List[Any]) :: tail => if (head.last == tail.head) packAny((head :+ tail.head) :: tail.drop(1)) else head :: packAny(tail)
    case head :: tail => if (head == tail.head) packAny(List(head) :: tail) else List(head) :: packAny(tail)
  }

이 문제는 더 좋은 방법이 있을 것 같은데, 찾게 된다면 수정하도록 하겠습니다!

---

P10. P09의 결과값을 사용하여 주어진 리스트를 Run-length encoding하여 반환하는 함수를 작성하시오.

Run-length encoding이란 데이터 압축 방법 중의 하나로, 연속하여 중복된 원소를 E, 중복된 횟수를 N이라고 할 때 (N,E) 형태의 튜플로 인코딩하는 것을 의미한다.

P10. Run-length encoding of a list. Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (N, E) where N is the number of duplicates of the element E.

 

P09의 결과값을 사용하여 주어진 리스트를 Run-length encoding 하는 함수를 작성하는 문제입니다.

런 렝스 부호화 - 위키백과, 우리 모두의 백과사전

우리는 이미 P09에서 주어진 리스트를 List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))와 같이 묶어두었습니다. 따라서 각각의 리스트에 대해서 (length, head) 형태의 튜플로 변환해주게 되면 간단히 답을 도출할 수 있습니다.

소스 코드는 다음과 같습니다 :

  def encode[T](list: List[T]): List[(Int, T)] = {
    def innerEncode[T](pList: List[List[T]]): List[(Int, T)] = pList match {
      case Nil => Nil
      case head :: tail => (head.length, head.head) :: innerEncode(tail)
    }
    innerEncode(pack(list))
  }

---

P11. P10의 결과값을 사용하여 주어진 리스트를 수정된 run-length encoding하여 반환하는 함수를 작성하시오. 수정된 run-length encoding이란 일반적인 run-length encoding과 같이 연속하여 중복된 원소를 (N,E) 형태의 튜플로 인코딩하나 중복되지 않은 원소는 튜플이 아닌 원소 그 자체만을 리스트에 삽입하는 방법을 의미한다. 즉, 연속하여 중복되어진 원소들만을 (N, E) 튜플 형태로 인코딩하도록 작성한다.

P11. Modified run-length encoding. Modify the result of problem P10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N, E) terms.

 

P11은 P10의 인코딩 형태에서 length가 1인 튜플은 튜플 형태가 아닌 원소 그 자체, 즉 T 타입으로 리스트 내에 포함시키면 되는 간단한 문제입니다. 즉, legnth가 1인 경우 (head.length, head.head) 가 아닌 head.head 를 반환해주면 됩니다.

소스 코드는 다음과 같습니다 : 

  def encodeModified[T](list: List[T]): List[Any] = {
    def innerEncodeModified[T](pList: List[List[T]]): List[Any] = pList match {
      case Nil => Nil
      case head :: tail => (if (head.length > 1) (head.length, head.head) else head.head) :: innerEncodeModified(tail)
    }
    innerEncodeModified(pack(list))
  }

---

P12. Run-length encoding 된 리스트를 디코딩하는 함수를 작성하시오. 입력으로는 P10의 인코딩 결과물이 주어지며, 출력으로는 P10에 입력된 것과 같이 압축되지 않은 리스트를 반환하도록 작성한다.

P12. Decode a run-length encoded list. Given a run-length code list generated as specified in problem P10, construct its uncompressed version.

 

이번 문제는 P10의 출력과 같이 Run-length 인코딩 된 배열을 디코딩하는 문제입니다. 디코딩은 인코딩보다 더 간단하게 작성할 수 있으며, 마찬가지로 head::tail 특성을 활용합니다. head._1, 즉 length를 하나씩 감소시키며 해당 원소를 리스트에 추가하고, 그 리스트에 다시 decode((head._1 -1, head._2) :: tail)를 붙여줍니다. 단, head._1이 0이라면 head를 제외하고 decode(tail)만을 붙여 주어야 합니다.

decode() 함수의 동작 원리

소스 코드는 다음과 같습니다 : 

  def decode[T](list: List[(Int, T)]): List[T] = list match {
    case Nil => Nil
    case head :: tail => if (head._1 > 0) head._2 :: decode((head._1 - 1, head._2) :: tail) else decode(tail)
  }

---

P13. P09의 pack 등 기존에 작성했던 솔루션들을 활용하지 말고 주어진 리스트를 Run-length encoding하여 반환하는 함수를 작성하시오.

P13. Run-length encoding of a list (direct solution). Implement the so-called run-length encoding data compression method directly. I.e. don't use other methods you've written (like P09's pack); do all the work directly.

 

이번 문제는 기존에 작성한 함수를 하나도 사용하지 않고 P10과 같은 결과물을 구현해내는 문제입니다. 이 문제를 구현하기 위해 P09와 비슷한 접근법을 사용했습니다. 리스트 내의 모든 원소들을 (1, elem) 형태로 변환해준 다음, tail이 Nil이 아니고, 즉 마지막 원소가 아닌 상태에서 tail.head._2와 head._2가 일치하는 경우에 head._1, 즉 length를 하나 증가시키는 방법으로 구현했습니다.

innerEncodeDirect() 함수의 동작 원리

소스 코드는 다음과 같습니다 :

  def encodeDirect[T](list: List[T]): List[(Int, T)] = {
    def innerEncodeDirect(tList: List[(Int, T)]): List[(Int, T)] = tList match {
      case Nil => Nil
      case head :: Nil => head :: Nil
      case head :: tail => if (head._2 == tail.head._2) innerEncodeDirect((head._1 + 1, head._2) :: tail.drop(1)) else head :: innerEncodeDirect(tail)
    }

    innerEncodeDirect(list.map(elem => (1, elem)))
  }