Lisa의 워크북 문제
n개의 챕터가 있는 워크북이 있고, 이 워크북의 매 페이지는 k 개 문제를 담을 수 있다.
이후에 n 개의 정수를 받는데 이는 각 챕터의 문제 수이다. 각 챕터의 문제는 1번 부터 시작하며,
새로운 챕터는 새 페이지에서 시작한다.
이 때, 문제번호와 페이지번호(1번부터 시작)가 같은 문제를 특별한 문제라고 할 때, 주어진 데이터 내에서 특별한 문제의 개수를 구하라는 내용이다.
풀이
이 문제는 하스켈에서 의외로 쉽게 풀린다. 다음과 같은 순서로 풀어보자.
- 숫자 x 를 받았을 때, [[1,2,3], [4,5,6], [7]] 과 같이 해당 챕터의 페이지 구성을 리턴하는 함수를 하나 작성한다.
- 입력받은 숫자들에 대해서 1의 함수를 맵핑하고, 이를
concat
으로 폴드한다. - 2의 결과를
[1..]
무한집합과 zipping 한다. 그러면(페이지번호, [문제번호])
로 구성된 리스트가 나오는데 - 3에서 페이지번호가 문제번호에 포함된 (
elem
함수를 쓴다) 것의 개수를 센다.
코드는 아래와 같다. 가장 기본이 되는 핵심 아이디어는 processChapter
를 구현하는 것인데, drop, take를 잘 써서 쉽게 구현할 수 있다.
import Control.Applicative
import Data.List
processChapter :: Int -> Int -> [[Int]]
processChapter k n = helper k [] [1..n]
where
helper :: Int -> [[Int]] -> [Int] -> [[Int]]
helper _ ys [] = reverse ys
helper k ys xs =
let ps = take k xs in helper k (ps:ys) (drop k xs)
solve :: [Int] -> Int
solve k xs = let ys = zip [1..] . concat . map (processChapter k) $ xs
in length [x | x <- ys, test x]
where test (a, bs) = elem a bs
main = do
[n,k] <- (map read . words) <$> getLine
s <- (solve k . map read . take n . words) <$> getLine
print s
그리드 검색 문제
h, w 를 입력받고, h개만큼의 줄을 입력받아 wxh 의 그리드를 구성한다.
이렇게 2개의 그리드를 입력받아서 (단, 이 때 두 번째 그리드가 더 작다)
큰 그리드 내에 작은 그리드가 있으면 YES, 없으면 NO를 출력한다.
풀이
a 타입의 요소로 이루어진 그리드는 [[a]]
로 나타낼 수 있다. 주어진 리스트의 특정 범위를 슬라이스할 수 있는 함수로부터 출발하면 특정 위치에서의 매칭 여부를 검사할 수 있고, 다시 이를 전체에 반복하여 결과를 얻을 수 있다.
역시나 T회만큼 반복하면서 그리드의 크기와 그리드 데이터를 입력받는 과정을 처리하기가 매우 불편하다.
import Control.Applicative
import Control.Monad
range (i, j) = take (j - i) . drop i
myLookupHelper :: (Eq a) => (Int, Int) -> [[a]] -> [[a]] -> Bool
myLookupHelper (x, y) ms ts =
let w = length . head $ ts
h = length ts
rs = range (y, y+h) . map (range (x, x+w)) $ ms
in rs == ts
myLookup :: (Eq a) => [[a]] -> [[a]] -> String
myLookup ms ts =
let mw = length . head $ ms
mh = length ms
tw = length . head $ ts
th = length ts
pos = [(x, y) | x <- [0..(mw-tw)], y <- [0..(mh-th)]]
in if any (\p -> myLookupHelper p ms ts) pos then "YES" else "NO"
solve :: IO String
solve = do
[mw, mh] <- (map (read :: String -> Int) . words) <$> getLine
ms <- forM [1..mw] (const getLine)
[tw, th] <- (map (read :: String -> Int) . words) <$> getLine
ts <- forM [1..tw] (const getLine)
return $ myLookup ms ts
main = do
n <- readLn :: IO Int
rs <- forM [1..n] $ (const solve)
putStrLn . unlines $ rs