투명한 기부를 하고싶다면 이 링크로 와보세요! 🥰 (클릭!)
바이낸스(₿) 수수료 평생 20% 할인받는 링크로 가입하기! 🔥 (클릭!)
http://aperiodic.net/phil/scala/s-99/
S-99: Ninety-Nine Scala Problems
As in the previous section, we will start with a skeleton file, logic1.scala, and add code to it for each problem. The difference here is that the file starts out almost empty. First of all, consult a good book on discrete mathematics or algorithms for a d
aperiodic.net
위 링크에 문제들이 싹 있고
이 포스트에서는 정답을 달아보도록 하겠다. ^_^
(28 번 까지만 풀고 그만 풀었으니 참고하시라 ㅠ_ㅠ)
같이 보도록 하자
P01 리스트의 마지막 원소 출력
List(1, 1, 2, 3, 5, 8).last
P02 리스트의 마지막의 바로 앞 원소 출력
List(1, 1, 2, 3, 5, 8).dropRight(1).last
List(1, 1, 2, 3, 5, 8).takeRight(2)(0)
등등 다 가능
P03 K 번째 리스트의 원소 찾기
List(1, 1, 2, 3, 5, 8)(2)
P04 리스트의 원소 개수 찾기
List(1, 1, 2, 3, 5, 8).length
P05 리스트 뒤집기
List(1, 1, 2, 3, 5, 8).reverse
P06 리스트가 팬린드롬인지 확인하기
def isPalindrome(elem: List[Any]): Boolean = {
if (elem.length <= 1) {
true
}
else if(elem.head == elem.last){
isPalindrome(elem.slice(1,elem.length-1))
}
else {
false
}
}
println(isPalindrome(List(1, 2, 3, 2, 1)))
P07 더러운 리스트 structure를 Flatten 하기
즉, List(List(1, 1), 2, List(3, List(5, 8))) 이런거 깔끔하게 만들기.
def flatten_func(elem: List[Any]): List[Any] = {
elem.flatMap(x => x match {
case el : List[Any] => flatten_func(el)
case el2 => List(el2)
})
}
flatten_func(List(List(1, 1), 2, List(3, List(List(5, 8), 8))))
ㅋㅋㅋㅋㅋㅋ 개힘들었다
P08
object HelloWorld extends App{
def compress[A](elem: List[A]): List[A] = {
elem.foldLeft(List[A]())((a,b)=>{
if(!a.isEmpty && a.last==b){
a
} else {
a++List(b)
}
})
}
println(compress(List('a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e')))
}
문법적인 참고 링크
https://docs.scala-lang.org/tour/polymorphic-methods.html
(질문) 맨 아래의 것은 오류가 난다.
가운데의 것은 오류가 안 난다.
def compress[A](elem: List[A]): List[A] = {
elem.foldLeft(List[A]()){(a,b)=>{
if(!a.isEmpty && a.last==b){
a
} else {
a++List(b)
}
}}
}
def compressFunctional[A](ls: List[A]): List[A] =
ls.foldRight(List[A]()) { (h, r) =>
if (r.isEmpty || r.head != h) h :: r
else r
}
def ErrorFunction[A](elem: List[A]): List[A] = {
elem.foldLeft(List[A]()){(a,b)=>{
if(!a.isEmpty && a.last==b){
a
} else {
a::b
}
}}
}왜냐..! ::의 경우 List에 적용되는 연산자인데, 왼쪽에 element 오른쪽에 List 가 들어가는 연산자이기 때문.
'a' :: 'b' :: Nil 의 경우에도 오른쪽 Nil(빈 리스트) 부터 합쳐지는 것이기 때문에 오류가 나지 않는 것.
* 참고 : 리스트를 이어 붙일 때 ::: 라는 연산자도 사용 가능 하다.
* 참고 : 리스트 원소 추가할 때, 뒤에 붙이는 연산자로써 :+ 라는 메소드가 있기는 하지만 리스트 길이에 비례하는 시간이 걸려서 잘 사용하지 않는다. (Head에 추가할 때는 상수 시간, tail 에 추가할 때는 선형 시간)
P09 리스트 안의 원소를 연속된 같은 알파벳끼리 pack 해라.
pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
=> List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))
def pack[A](elem:List[A]) : List[List[A]] = {
if(elem.isEmpty){
List()
}
else{
val (packed_front,last) = elem.span((x) => {x==elem.head})
packed_front :: pack(last)
}
}
println(pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)))Pack의 경우에는
리스트를 여러 방법으로 자르는 참고링크
https://alvinalexander.com/scala/how-to-split-sequences-subsets-groupby-partition-scala-cookbook
P10 P09의 결과를 사용하여 Run-length Encoding을 진행해봐.
encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
=> List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))
def pack[A](elem:List[A]) : List[List[A]] = {
if(elem.isEmpty){
List()
}
else{
val (packed_front,last) = elem.span((x) => {x==elem.head})
packed_front :: pack(last)
}
}
def make_tuple[A](elem:List[List[A]]) : List[(Int,A)] = {
val head = (elem.head.length, elem.head.head)
if(elem.length == 1){
List(head)
} else head :: make_tuple(elem.drop(1))
}
def encode[A](elem:List[A]) : List[(Int,A)] = {
val packed = pack(elem)
make_tuple(packed)
}
println(encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)))이렇게 정답을 적어놓고 보니, 더 좋은 방법이 있었다
def pack[A](elem:List[A]) : List[List[A]] = {
if(elem.isEmpty){
List()
}
else{
val (packed_front,last) = elem.span((x) => {x==elem.head})
packed_front :: pack(last)
}
}
def encode[A](elem:List[A]) : List[(Int,A)] = {
val packed = pack(elem)
packed.map( x => {(x.length,x.head)})
}
println(encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)))
P11 P10의 결과와 다르게 좀더 수정 해 봐라
scala> encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Any] = List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e))
def pack[A](elem:List[A]) : List[List[A]] = {
if(elem.isEmpty){
List()
}
else{
val (packed_front,last) = elem.span((x) => {x==elem.head})
packed_front :: pack(last)
}
}
def encode[A](elem:List[A]) : List[Any] = {
val packed = pack(elem)
packed.map( x => {
if(x.length==1){
x.head
} else {
(x.length, x.head)
}
})
}
println(encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)))
P12 run-length encode를 디코딩 해 봐라.
scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)
def decode[A](elem:List[(Int,A)]):List[A] = {
if(elem.isEmpty){
List()
} else {
List.fill(elem.head._1)(elem.head._2) ::: decode(elem.drop(1))
}
}
println(decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e))))
List.fill 이라는 함수는 a번만큼 b를 복사한 list를 만들어주는 함수이다. ㅎㅎ
P13 list 의 Run-length encoding을 이전 함수들을 사용하지 말고 바로 해 봐라. (P09의 결과같은거 쓰지 말고)
scala> encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))
def encodeDirect[A](elem:List[A]):List[Any] = {
if(elem.isEmpty) {
Nil
} else {
val (front, last) = elem.span((x) => {
x == elem.head
})
(front.length, front.head) :: encodeDirect(last)
}
}
println(encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)))
P14 List의 element를 복제해라
scala> duplicate(List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)
def duplicate[A](el:List[A]):List[A] = {
if(el.isEmpty) Nil
else {
el.head :: el.head :: duplicate(el.drop(1))
}
}
println(duplicate(List('a, 'b, 'c, 'c, 'd)))
def duplicate[A](ls: List[A]): List[List[Any]] = ls map { e => List(e, e) }
println(duplicate(List('a, 'b, 'c, 'c, 'd)).flatten) def duplicate[A](ls: List[A]): List[Any] = ls flatMap { e => List(e, e) }
println(duplicate(List('a, 'b, 'c, 'c, 'd)))여러 답안 가능
P15 숫자가 주어지면 그 만큼 복제하기
scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)
def duplicateN[A](num: 3, list: List[A]) = {
list flatMap {x => {List.fill(num)(x)}}
}
println(duplicateN(3, List('a, 'b, 'c, 'c, 'd)))P16 (**) Drop every Nth element from a list.
Example:
scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)
def drop[A](num: Int, list: List[A]):List[A] = {
def dropCnt(cnt:Int, partial_list:List[A]) : List[A]= {
if(partial_list.isEmpty) Nil
else if(cnt==1) dropCnt(num,partial_list.drop(1))
else partial_list.head::dropCnt(cnt-1,partial_list.drop(1))
}
dropCnt(num, list)
}
println(drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)))
P17 (*) Split a list into two parts.
The length of the first part is given. Use a Tuple for your result.
Example:
scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
def split[A](num:Int,list:List[A]):(List[A],List[A]) = {
list.splitAt(num)
}
println(split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)))
P18 (**) Extract a slice from a list.
scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g)
def slice[A](num:Int,num2:Int,list:List[A]):List[A] = {
list.slice(num,num2)
}
println(slice(3,7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)))
P19 (**) Rotate a list N places to the left.
Examples:scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)
scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)
귀찮아서 양수만 구현
def rotate[A](num:Int,list:List[A]):List[A] = {
list.drop(num)++list.take(num)
}
println(rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)))
P20 (*) Remove the Kth element from a list.
scala> removeAt(1, List('a, 'b, 'c, 'd))
res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)
def removeAt[A](num:Int,list:List[A]):(List[A],A) = {
(list.take(num):::list.drop(num + 1),list(num))
}
println(removeAt(1, List('a, 'b, 'c, 'd)))P21 (*) Insert an element at a given position into a list.
scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)
def insertAt[A](data:A, num:Int,list:List[A]):List[A] = {
(list.take(num):::data::
list.drop(num))
}
println(insertAt('new, 1, List('a, 'b, 'c, 'd)))
P22 (*) Create a list containing all integers within a given range.
Example:
scala> range(4, 9)
res0: List[Int] = List(4, 5, 6, 7, 8, 9)
def unFoldRight[A,B]( s: B )( f : B => Option[(A,B)] ):List[A]={
f(s) match {
case None => Nil
case Some((r,n)) => r :: unFoldRight(n)(f)
}
}
def rangeFunctional(start:Int,end:Int):List[Int] = {
unFoldRight(start){ n =>
if (n > end) None
else Some((n,n+1)) // 리스트에 추가할 것, 다음 함수의 입력을 튜플로 보내준다.
}
}
println(rangeFunctional(4,9))조은 정답이 있어서 가져와 봤다.
원래같으면 List.range(start,end) 이렇게 하면 한큐에 된다.
P23 (**) Extract a given number of randomly selected elements from a list.
Example:scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res0: List[Symbol] = List('e, 'd, 'a)
def randomSelect[A](num:Int, el: List[A]):List[A]={
println(el)
if(num == 0){
Nil
} else {
val rand = util.Random
val select = rand.nextInt(el.length)
el(select) :: randomSelect(num-1, el.take(select) ++ el.drop(select+1))
}
}
P24 (*) Lotto: Draw N different random numbers from the set 1..M.
scala> lotto(6, 49)
res0: List[Int] = List(23, 1, 17, 33, 21, 37)
def randomSelect[A](num:Int, el: List[A]):List[A]={
if(num == 0){
Nil
} else {
val rand = util.Random
val select = rand.nextInt(el.length)
el(select) :: randomSelect(num-1, el.take(select) ++ el.drop(select+1))
}
}
def lotto(num:Int, range:Int):List[Int]={
randomSelect(num,List.range(1,range))
}
println(lotto(6,49))
P25 (*) Generate a random permutation of the elements of a list.
def randomSelect[A](num:Int, el: List[A]):List[A]={
if(num == 0){
Nil
} else {
val rand = util.Random
val select = rand.nextInt(el.length)
el(select) :: randomSelect(num-1, el.take(select) ++ el.drop(select+1))
}
}
def randomPermute[A](li:List[A]):List[A]={
randomSelect(li.length,li)
}P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list.
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient). For pure mathematicians, this result may be great. But we want to really generate all the possibilities.
Example:
scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), ...
def dropKth[A](idx:Int,li:List[A]):List[A]={
li.take(idx)++li.drop(idx+1)
}
def combinations[A](num:Int, li:List[A]):List[List[A]]={
if(num==0) List(List())
else {
for{
x <- List.range(0,li.length)
y <- {
combinations(num - 1, dropKth(x, li))
}
} yield li(x)::y
}
}
println(combinations(3, List('a, 'b, 'c, 'd, 'e, 'f)))위 처럼 하면 모든 퍼뮤테이션이 구해진다.
def combination[A](num: Int, li: List[A]): List[List[A]] = {
if (num == 0) {
List(Nil)
}
else {
li match {
case head :: tail =>
combination(num - 1, tail).map(head :: _) ++ combination(num, tail)
case Nil =>
Nil
}
}
}요로케 하면 모든 컴비네이션이 구해진다.
P27 (**) Group the elements of a set into disjoint subsets.
a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities.
Example:
scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David, Evi), List(Flip, Gary, Hugo, Ida)), ...
b) Generalize the above predicate in a way that we can specify a list of group sizes and the predicate will return a list of groups.
Example:
scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo, Ida)), ...
Note that we do not want permutations of the group members; i.e. ((Aldo, Beat), ...) is the same solution as ((Beat, Aldo), ...). However, we make a difference between ((Aldo, Beat), (Carla, David), ...) and ((Carla, David), (Aldo, Beat), ...).
You may find more about this combinatorial problem in a good book on discrete mathematics under the term "multinomial coefficients".
설명이 길어 요약하자면, 콤비네이션 세트를 구현해보라는 뜻.
def group[A](cnts:List[Int], li:List[A]):List[List[List[A]]] = {
cnts match {
case Nil => List(Nil)
case head :: tail => combination(head, li) flatMap {
x => {
group(tail,li diff x).iterator.map {
y => x :: y
}
}
}
}
}
println(group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida")))너모 힘들어
정답보고 다시풀엇다
P28 (**) Sorting a list of lists according to length of sublists.
a) We suppose that a list contains elements that are lists themselves. The objective is to sort the elements of the list according to their length. E.g. short lists first, longer lists later, or vice versa.
Example:
scala> lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res0: List[List[Symbol]] = List(List('o), List('d, 'e), List('d, 'e), List('m, 'n), List('a, 'b, 'c), List('f, 'g, 'h), List('i, 'j, 'k, 'l))
리스트를 리스트의 길이 순으로 소트해라.
def lsort[A](lists:List[List[A]]):List[List[A]] = {
lists.sortWith((a,b) => {
a.length < b.length
})
}
println(lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o))))
b) Again, we suppose that a list contains elements that are lists themselves. But this time the objective is to sort the elements according to their length frequency; i.e. in the default, sorting is done ascendingly, lists with rare lengths are placed, others with a more frequent length come later.
Example:
scala> lsortFreq(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res1: List[List[Symbol]] = List(List('i, 'j, 'k, 'l), List('o), List('a, 'b, 'c), List('f, 'g, 'h), List('d, 'e), List('d, 'e), List('m, 'n))
Note that in the above example, the first two lists in the result have length 4 and 1 and both lengths appear just once. The third and fourth lists have length 3 and there are two list of this length. Finally, the last three lists have length 2. This is the most frequent length.
def unfoldMapWithKey[A,B](map:Map[B,List[A]]):List[(Int,List[A])]={
if(map.isEmpty) Nil
else {
(map.head._2.length,map.head._2)::unfoldMapWithKey(map.drop(1))
}
}
def lsortFreq[A](lists:List[List[A]]):List[List[A]] = {
unfoldMapWithKey(lists.groupBy(x=>x.length)).sortWith((x,y)=>(x._1<y._1)).flatMap({
x=> x._2
})
}
println(lsortFreq(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o))))위와 같이 풀었는데 저 unfoldMapWithKey를 대체 가능한 몇몇 방법들이 또 있는 것 같다.
def unfoldMapWithKey2[A,B](map:Map[B,List[A]]):List[(Int,List[A])]= {
val new_list = List(map).flatMap(x=>x).map(k=>(k._2.length,k._2))
println(new_list)
new_list
}
// 위 방법과는 조금 다르게 풀리지만 여튼 해결은 된다.
// List((1,List(List('o))), (3,List(List('d, 'e), List('d, 'e), List('m, 'n))), (2,List(List('a, 'b, 'c), List('f, 'g, 'h))), (1,List(List('i, 'j, 'k, 'l))))
종범님이 몇가지 더 짧은 스킬을 알려줬다
def unfoldMapWithKey3[A,B](map:Map[B,List[A]]):List[(Int,List[A])]= {
val new_list = map.values.toList.map(k=>(k.length,k))
println(new_list)
new_list
}
def unfoldMapWithKey4[A,B](map:Map[B,List[A]]):List[(Int,List[A])]= {
val new_list = List.from(map).map(k=>(k._2.length,k._2))
println(new_list)
new_list
}
이제 그만할란다
나머지는 ㅎㅇㅌ!
https://books.underscore.io/scala-with-cats/scala-with-cats.pdf
이거 읽으러 갈 것
