(연습문제) 리사의 워크북 문제

Lisa의 워크북 문제

https://www.hackerrank.com/challenges/bear-and-workbook

n개의 챕터가 있는 워크북이 있고, 이 워크북의 매 페이지는 k 개 문제를 담을 수 있다.
이후에 n 개의 정수를 받는데 이는 각 챕터의 문제 수이다. 각 챕터의 문제는 1번 부터 시작하며,
새로운 챕터는 새 페이지에서 시작한다.

이 때, 문제번호와 페이지번호(1번부터 시작)가 같은 문제를 특별한 문제라고 할 때, 주어진 데이터 내에서 특별한 문제의 개수를 구하라는 내용이다.

풀이

이 문제는 하스켈에서 의외로 쉽게 풀린다. 다음과 같은 순서로 풀어보자.

  1. 숫자 x 를 받았을 때, [[1,2,3], [4,5,6], [7]] 과 같이 해당 챕터의 페이지 구성을 리턴하는 함수를 하나 작성한다.
  2. 입력받은 숫자들에 대해서 1의 함수를 맵핑하고, 이를 concat으로 폴드한다.
  3. 2의 결과를 [1..] 무한집합과 zipping 한다. 그러면 (페이지번호, [문제번호])로 구성된 리스트가 나오는데
  4. 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