Scala-99-Problems 솔루션 : P01 ~ P04

이미지 출처 : Pixabay

안녕하세요!

Scala 공부를 위해, 스칼라로 작성된 코딩 테스트 문제를 풀고 있습니다.

Phil Gold의 99-Scala-Problems를 정리해 둔 다음 git을 clone하여 하나씩 문제를 풀고 있습니다.

S-99: Ninety-Nine Scala Problems

99XProblems/99-Scala-Problems

 

작성된 솔루션은 제 git에서 확인하실 수 있습니다.

SeanMa-kr/99-Scala-Problems

 

부족한 실력이지만 스칼라를 공부하시는 분들께 도움이 되지 않을까 하여 글을 작성해 봅니다.

가장 간단한, 리스트에서 원소를 찾는 문제들인 P01 ~ P04 에 대한 솔루션입니다 : 

 

 

---

P01. 리스트에서 마지막 원소를 반환하는 함수를 작성하시오.

 

last(List(1, 1, 2, 3, 5, 8)) 함수를 실행하면 8이 반환되도록 작성되어야 합니다.

이를 스칼라에서 제공하는 함수를 사용하지 않고 작성하기 위해 스칼라에서 리스트가 어떻게 구성되는지 파악하고 있어야 합니다.

List(1, 2, 3)은 실제로 1 과 List(2, 3), 그리고 2와 List(3), 그리고 3과 리스트의 마지막인 Nil이 연결된 형태로 구성되어 있습니다.

풀어쓰면, 스칼라의 리스트는 1 :: (2 :: (3 :: Nil)) 과 같이 구성되어 있다는 것을 확인할 수 있습니다. 즉, 스칼라의 리스트는 head :: tail 의 연속이라고 생각하시면 되겠습니다.

1 :: (2 :: (3 :: Nil)) 에서 1이 head, (2 :: (3 :: Nil))이 tail이 되고, 다시 이 tail의 head는 2, tail은 (3 :: Nil)이 됩니다.

글로만 쓰면 되게 난해한 개념이라 이해하기 쉽게 그림으로 풀어보면 다음과 같습니다.

List의 head :: tail 구조

따라서, List[T]는 Head:T, Tail:List[T] 와 같은 형식으로 구성됩니다.

이제 이러한 리스트의 특성을 사용하여, 리스트를 시작부터 마지막까지 순회하며 tail == Nil 일 경우, 이 때 head가 리스트의 마지막 원소임을 확인할 수 있습니다.

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

  @tailrec
  def last[T](list: List[T]): T = list match {
    case Nil => throw new NoSuchElementException
    case head :: tail => if (tail == Nil) head else last(tail)
  }

 

---

P02. 리스트에서 마지막에서 두 번째에 위치한 원소를 반환하는 함수를 작성하시오.

 

마찬가지로, P01과 같은 특성을 사용합니다.

대신, 이번에는 해당 원소 , 그 다음 원소 뒤에 Nil이 위치하는지를 확인해 줍니다.

head :: _ :: tail 의 의미

head 뒤에 하나의 원소가 더 존재하고, 그 뒤에 tail이 존재할 경우, head를 반환하면 되겠습니다.

  @tailrec
  def penultimate[T](list: List[T]): T = list match {
    case Nil => throw new NoSuchElementException
    case head :: _ :: Nil => head
    case _ :: tail => penultimate(tail)
  }

---

P03. 리스트에서 K번째 원소를 반환하는 함수를 작성하시오. (편의상, 리스트의 첫 번째 인덱스는 0으로 함)

 

역시 head :: tail 특성을 활용합니다.

nth 파라미터로 들어온 값을 하나씩 감소시키면서 0이 될 때 head의 값을 반환한다면 리스트의 k번째 원소를 반환할 수 있습니다.

nth() 함수의 작동 원리

  @tailrec
  def nth[T](list: List[T], n: Int): T = list match {
    case Nil => throw new NoSuchElementException
    case head :: tail => if (n > 0) nth(tail, n - 1) else head
  }

---

P04. 리스트 내의 원소의 갯수를 구하는 함수를 작성하시오.

 

이번 문제틑 리스트 내에서 특정 원소를 반환하는게 아니라 원소의 '갯수'를 반환하여야 합니다.

마찬가지로 head :: tail 구조를 Nil이 나올 때 까지 순환합니다.

다만 이전 nth 문제와는 달리 값을 하나씩 증가시켜야 합니다.

부가적인 함수를 정의하지 않기 위해 증가시킨 값을 param으로 전달하지 말고, 1 + length(List) 형식으로 재귀적으로 작성하도록 합니다.

length 함수의 작동 원리

  def length[T](list: List[T]): Int = list match {
    case Nil => 0
    case _ :: tail => 1 + length(tail)
  }

P04의 솔루션은 꼬리재귀가 아니기 때문에 @tailrec 어노테이션을 붙이지 않도록 주의합니다.