연속으로 주어진 숫자들이 n개 있으면 이 숫자들의 간격이 1부터 n-1까지 종류별로 모두 있는 경우를 졸리 점퍼(Jolly jumper)라고 부른다. 예를 들어 1 4 2 3이라는 4개의 숫자가 있을 때 1과 4의 간격은 3, 4와 2의 간격은 2, 2와 3의 간격은 1로 1에서 3까지 모두 있다.
숫자 리스트를 입력 받아 졸리 점퍼인지 판단하는 프로그램을 작성하라.
module Main where import List(sort) diff (x:y:zs) = x-y : diff (y:zs) diff [_] = [] jolly = all (-1==) . diff . sort . absdiff where absdiff = map abs . diff main = do input <- getLine let list = map read (words input) putStrLn (if jolly list then "Jolly" else "Not Jolly")
all 함수는 주어진 리스트의 모든 원소가 조건에 맞으면 True, 하나라도 예외가 있으면 False를 반환한다. 비슷한 함수로 any가 있는 데 all과 반대로 조건에 맞는 원소가 하나라도 있으면 True, 그렇지 않으면 False를 반환한다.
; 두 값의 차이를 구함 (defun difference (x y) (abs (- x y))) ; 리스트내 인접한 두 요소의 차이를 요소로 하는 리스트 (defun successive-diff (lst) (cond ((null lst) nil) ((< (length lst) 2) nil) (T (cons (difference (first lst) (second lst)) (successive-diff (cdr lst)))))) ; 해당 리스트의 모든 요소가 1씩 증가하는지 검사 (defun inc-by-1 (lst) (cond ((null lst) t) ((< (length lst) 2) t) (t (and (= (+ 1 (first lst)) (second lst)) (inc-by-1 (cdr lst)))))) (defun jollyp (lst) (inc-by-1 (sort (remove-duplicates (cons (- (length lst) 1) (cons 1 (successive-diff lst)))) #'<)))
제가 haskell 코드를 제대로 이해했는지는 모르겠습니다만...
의도로 봐서는 차이값을 가지고 sort한 리스트를 만들고, 그 리스트의 원소가 모두 1씩 차이가 나는지를 검사하는 것으로 생각됩니다만...
그러면 다음과 같은 리스트의 경우에 잘못 판단되지 않을까 싶은데요...
[ 2 4 7 11 16 ]
이런 수열일 경우, 차이값은 [ 2 3 4 5 ]로 나오게 될텐데, 문제의 정의는 1 ~ n-1 까지의 수가 나와야 한다고 했으니 이 경우는 부정되어야 하지않을까요?
맞습니다. 위의 코드에서 jolly 함수를 다음과 같이 고치면 됩니다.
jolly = and . zipWith (==) [1..] . sort . map abs . diff
jollyList [_] = [] jollyList (x:y:zs) = abs (x - y) : jollyList(y:zs) isJolly xs = [next,next-1..1] == jollyList xs where next = length xs - 1
조금 고쳐봤습니다.
module Base where import List(sort) jollyList [_] = [] jollyList (x:y:zs) = abs (x - y) : jollyList(y:zs) isJolly xs = [1..(length xs - 1)] == sort (jollyList xs)
import List jollyList [_] = [] jollyList (x:y:zs) = abs (x - y) : jollyList(y:zs) isJolly xs = [1..next] == sorted where next = length xs - 1 sorted = sort (jollyList xs)
from. http://blog.daum.net/sizuha/2792737 저는 중복 검사를 이용해서 풀었습니다.
Array>>isJollyJumper | prev num_list distance | (self size < 2) ifTrue: [ ^false ]. prev := self first. num_list := Array new: (self size) withAll: false. self collect: [ :each | distance := (prev - each) abs + 1. (distance > num_list size) ifTrue: [ ^false ]. (num_list at: distance) ifTrue: [ ^false ]. num_list at: distance put: true. prev := each. ]. ^true.
하스켈 버전
module Main where import List(sort) diff (x:y:zs) = x-y : diff (y:zs) diff [_] = [] jolly = all (-1==) . diff . sort . absdiff where absdiff = map abs . diff main = do input <- getLine let list = map read (words input) putStrLn (if jolly list then "Jolly" else "Not Jolly")all 함수는 주어진 리스트의 모든 원소가 조건에 맞으면 True, 하나라도 예외가 있으면 False를 반환한다. 비슷한 함수로 any가 있는 데 all과 반대로 조건에 맞는 원소가 하나라도 있으면 True, 그렇지 않으면 False를 반환한다.
리스프 버전
최적화 좀 해주세용~ *^^*
한가지 의문?
제가 haskell 코드를 제대로 이해했는지는 모르겠습니다만...
의도로 봐서는 차이값을 가지고 sort한 리스트를 만들고, 그 리스트의 원소가 모두 1씩 차이가 나는지를 검사하는 것으로 생각됩니다만...
그러면 다음과 같은 리스트의 경우에 잘못 판단되지 않을까 싶은데요...
[ 2 4 7 11 16 ]
이런 수열일 경우, 차이값은 [ 2 3 4 5 ]로 나오게 될텐데, 문제의 정의는 1 ~ n-1 까지의 수가 나와야 한다고 했으니 이 경우는 부정되어야 하지않을까요?
맞습니다. 위의
맞습니다. 위의 코드에서 jolly 함수를 다음과 같이 고치면 됩니다.
[하스켈]맞는지 모르겠습니다. ㅡ ㅡ)
수정판 Haskell Code
조금 고쳐봤습니다.
수정했습니다.ㅎㅎ
Smalltalk Code
from. http://blog.daum.net/sizuha/2792737
저는 중복 검사를 이용해서 풀었습니다.
Array>>isJollyJumper | prev num_list distance | (self size < 2) ifTrue: [ ^false ]. prev := self first. num_list := Array new: (self size) withAll: false. self collect: [ :each | distance := (prev - each) abs + 1. (distance > num_list size) ifTrue: [ ^false ]. (num_list at: distance) ifTrue: [ ^false ]. num_list at: distance put: true. prev := each. ]. ^true.