Scala Map을 이용한 Secondary Sort

Scala에서의 대표적인 데이터 구조가 바로 Map입니다. 어느 프로그래밍 언어이건 간에 가장 대표적인 데이터 구조로 손꼽히는데, 먼저 이 Map에 데이터를 집어넣어 봅시다.

scala> val map = Map("a" -> 1, "b" -> 1, "c" -> 2)
map: scala.collection.immutable.Map[String,Int] = Map(a -> 1, b -> 1, c -> 2)

Functional Programming에 본격적으로 들어가면서부터 Immutable, 즉 변형 불가능한 데이터 구조들이 등장하기 시작합니다. 일단은 여기서 깊이 들어가지는 않고 넘어가겠습니다.

일단은 Map 자체로는 정렬을 할 수가 없습니다. 따라서 Map을 (key, value)의 tuple 형태로 List로 먼저 뽑아내야 합니다. 이는 toSeq로 쉽게 변경할 수 있습니다.

scala> map.toSeq
res3: Seq[(String, Int)] = ArrayBuffer((a,1), (b,1), (c,2))

만약 이 Tuple을 Value 기준으로 내림차순, Key 기준으로 오름차순으로 정렬하고 싶다면,

scala> map.toSeq.sortWith((t1, t2) => if (t1._2 == t2._2) t1._1 < t2._1 else t1._2 > t2._2)
res2: Seq[(String, Int)] = ArrayBuffer((c,2), (a,1), (b,1))

이렇게 Secondary Sort를 자유 자재로 줄 수 있습니다.
함수 내용을 간단히 설명하면, 두 개의 비교할 tuples, 즉 t1과 t2를 가지고 value(._2)가 같다면 key(._1)를 기준으로 오름차순 정렬하고, 나머지 경우에 대해서는 value를 기준으로 내림차순 정렬하는 함수입니다 🙂

가장 간단하면서도 가장 필수적인 스킬중의 하나입니다.

Functional Programming : sliding

출처 : https://www.hackerrank.com/challenges/the-birthday-bar

개의 초콜릿이 있고, 그 위에는 정수 하나씩이 적혀있습니다.

개의 초콜릿을 순서대로 골라 합이 가 되는 경우의 수를 구하고자 합니다.
이 때도 물론 우리가 주구장창 배워왔던 방법으로 코딩을 해도 되지만, functional programming을 이용해 보려고 합니다.
sliding이라는 함수는 list에서 size크기의 window를 만들어 step만큼씩 뛰어가면서 window sliding을 하게 됩니다.

위의 그림을 보면 좀 컨셉이 와 닿으시죠? 그러면 어떻게 코드로 구현하는지 살펴봅시다.

val result = squares.sliding(m, 1).foldLeft(0) {
    (count, window) =>
        if (window.sum == d) count+1
        else count
}

sliding 함수를 쓰면 크기가 m인 윈도우로 한개씩 옆으로 가면서 나오는 부분 리스트들이 iterator 형태로 반환되는데요, 거기서 foldLeft를 써서 초기 결과값 0을 시작으로 몇 개의 부분 리스트의 합이 d가 되는지를 위와 같이 구할 수 있습니다.

참 깔끔하고 좋죠?

Functional Programming : FoldLeft

출처 : https://www.hackerrank.com/challenges/breaking-best-and-worst-records

한 농구 선수가 있습니다. 이 선수는 자신의 시즌 동안의 경기당 득점을 기록해나가기로 다짐합니다. 결국 득점들은 이런 형태로 기록될 것입니다.

경기를 해나가면서 그때그때 최고득점을 경신했는지, 최소득점을 경신했는지를 센다고 하면, 득점 기록이 주어졌을 때 어떻게 셀 수 있을까요~?

예를 들어, [10, 5, 20, 20, 4, 5, 2, 25, 1]가 주어졌다고 하면, 최소득점은 2번째, 5번째, 7번째, 9번째 경기에서 경신했구요, 최대득점은 3번째, 8번째에서 경신했습니다. 따라서,

최대득점 : 2번 경신

최소득점 : 4번 경신

이 됩니다. 물론 리스트를 받았을 때, for문으로 classic하게 count 값을 추적하면서 구해낼 수도 있을 것입니다. 하지만 빅데이터를 다룰 때는 functional programming이 매우 중요하므로 이 방법을 써서 구해 보도록 하겠습니다.

// scores가 득점 기록이 담긴 list라고 가정합시다.
val record = scores.tail.foldLeft((scores.head, 0, scores.head, 0)) 
{ (r, score) =>
    if (score > r._1) (score, r._2 + 1, r._3, r._4)
    else if (score < r._3) (r._1, r._2, score, r._4 + 1)
    else r
}
printf("%d %d\n", record._2, record._4) // 최고기록 경신, 최소기록 경신 순으로 출력합니다.

여기서 foldLeft는 주어진 초기값(scores.head, 0, scores.head, 0)을 바탕으로 리스트의 왼쪽 원소부터 연산을 진행해 나갑니다. 돗자리를 왼쪽부터 말아간다고 생각하시면 편할 것 같네요. scores.head를 통해서 첫번째 경기의 득점을 가지고 오구요, r은 4개의 원소로 이루어진 tuple을 의미합니다. (돗자리를 말아가면서 계속 keep해 나갈 counter라고 생각하시면 됩니다.) 중간의 if else문을 보시면 tuple의 첫번째 원소가 현재까지의 최고 기록이고, tuple의 두번째 원소가 최고 기록 경신 횟수, tuple의 세번째 원소가 현재까지의 최저기록, tuple의 마지막 원소가 현재까지의 최저 기록 경신 횟수입니다.

간단한 문제일 수도 있지만, 전혀 다른 functional programming 방법을 사용해서 코딩해 보았습니다. 영감이 오지 않나요!?