Scala-99-Problems 솔루션 : P05 ~ P07

이미지 출처 : Pixabay

지난 글에서는 가장 기본적인 리스트 내에서 원소를 찾는 문제들인 P01~P04에 대한 솔루션을 작성하였습니다.

P08~P13 의 내용이 리스트 내 중복 제거 및 Run-length encoding에 대한 내용이라 해당 내용들을 한번에 묶어서 정리하기 위해 이번 글에서는 P05~P07 까지의 솔루션에 대해 작성하려 합니다.

---

P05. 리스트 내 원소들의 순서가 반전된 리스트를 반환하는 함수를 작성하시오.

P05. Reverse a list.

 

저는 재귀적으로 작성하는 솔루션을 선호해 이번 문제에서도 list의 head::tail 특성을 활용하였습니다.

재귀적으로 맨 앞 head를 Nil이 나올 떄 까지 tail에 마지막에 이어붙인다면 리스트 전체가 반전됩니다.

head를 tail에 append

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

  def reverse[T](list: List[T]): List[T] = list match {
    case Nil => list
    case head :: tail => reverse(tail) :+ head
  }

---

P06. 주어진 리스트가 회문인지 판별하는 함수를 작성하시오.

P06. Find out whether a list is a palindrome.

 

회문(palindrome) 이란 거꾸로 읽어도 정방향으로 읽은 것과 같은 문장, 낱말 등을 의미합니다.

회문 여부를 판단하기 위해서는 문자열에서 맨 앞과 뒤의 원소를 순서대로 비교하면서 소거해 나갔을 때, 하나의 원소만 남거나 딱 맞아 떨어지는지를 확인하면 됩니다.

예를 들면, 

a, b, c, b, a -> a ~ a

b, c, b -> b ~ b

c -> //하나만 남았으므로 회문임.

 

a, b, c, c, b, a -> a ~ a

b, c, c, b -> b ~ b

c, c, -> c~ c //딱 맞아떨어지므로 회문임.

 

a, b, c, d, a -> a ~ a

b, c, d -> b ~ d //일치하지 않으므로 회문이 아닙니다.

 

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

재귀적으로 작성한 회문 판별법

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

  @tailrec
  def isPalindrome[T](list: List[T]): Boolean = list match {
    case Nil => true
    case _ :: Nil => true
    case head :: tail => if (tail.last == head) isPalindrome(tail.dropRight(1)) else false
  }

---

P07. 중첩된 구조의 리스트를 평탄화(flatten) 하는 함수를 작성하시오.

P07. Flatten a nested list structure.

 

중첩된 리스트는 List[T], List[List[T]] 등과 T 타입이 섞여 List[Any] 타입을 가집니다. 이를 평탄화하면 List[T] 타입을 갖게 됩니다.

그렇다면 List(List(1,List(2)),3,List(4))는 다음 그림처럼 나타낼 수 있겠습니다.

List(List(1, List(2)), 3, List(4))

위 그림에서 회색 바운더리를 List라고 했을 때, 회색 바운더리들만 제거해 주면 List(1,2,3,4)를 얻을 수 있을 것 같습니다.

마찬가지로 head::tail 특성을 이용해 접근합니다.

List(List(1,List(2)),3List(4))의 Head는 List(1,List(2)) 이고 Tail은 List(3,List(4)) 입니다.

만일 flatten 함수에 저 바운더리(리스트)가 입력된다면 바운더리를 한겹 벗긴 후 출력하고, 그렇지 않다면 그대로를 출력한다고 가정합시다.

그런 flatten 함수가 있다면 저 리스트에 flatten(head) :: flatten(tail)을 적용시키면 head의 바운더리가 한 겹 벗겨지게 되고 그런 head에 tail을 이어주는 꼴이 되지 않을까요?
복잡하니 그림으로 한번 더 확인해봅시다.

flatten(List(1, List(2)) :: flatten(List(3, List(4))

List(List(1, List(2))의 리스트가 한 겹 벗겨져 List(1, List(2))의 형태가 되었습니다.

이제 각각의 리스트들에 대해서 head의 타입이 T이기 때문에 tail에 flatten(tail) 함수를 적용해 주면 될 것 같습니다.

즉, 입력 Any에 대해 Head의 타입이 T라면 head :: flatten(tail)을, Head의 타입이 T가 아니라면 flatten(head) :: flatten(tail)을 적용해 재귀적으로 연산을 수행해 주면 저 리스트들이 제거될겁니다.

 

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

  def flatten[T](list:List[Any]):List[T] = list match {
    case Nil => Nil
    case (head: List[T]) :: tail => flatten(head) ::: flatten(tail)
    case (head:T) :: tail => head :: flatten(tail)
  }