태그 보관물: Haskell

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

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

(연습문제) 행렬의 대각선의 차

대각선의 차이 구하기

N*N 크기의 행렬이 주어졌을 때, 이 행렬의 대각선상에 위치하는 요소들의 합끼리의 차를 구하는 프로그램을 작성하는 문제이다.

https://www.hackerrank.com/challenges/diagonal-difference

i 번째 행의 (i-1)번, 및 (N-i)번 인덱스의 값을 각각 뺀 다음 (i=1,2,3… 인덱스는 0, 1, 2 순) 이들을 합산하고 절대값을 취하면 된다.

module Main where

import Control.Monad
import Control.Applicative

-- i 와 i번 행을 받아 이를 처리한다. 
processLine :: Int -> [Int] -> Int
process i xs = let a = head $ drop (i-1) xs
                   b = head . drop (i-1) . reverse $ xs
                in a - b

main = do
  n <- readLn :: IO Int
  ts <- sum <$> forM [1..n] (\x -> processLine x . map read . words <$> getLine)
  print . abs $ ts

여기서도 <$> 연산자를 유용하게 썼고, forM 함수도 썼다.

forM, <$>

forM 함수는 (Monad m, Traversable t) => t a -> (a -> m b) -> m (t b)의 타입을 가진 함수로 리스트나 트리와 같은 순회 가능한 목록과 모나딕 값을 리턴하는 함수를 이용해서 리스트의 각 원소를 처리하고, 이를 모나딕 리스트나 모나딕 트리로 리턴하는 함수이다.

여기서 두 번째 인자로 쓰인 함수를 살펴보면

(\x -> processLine x . map read . words <$> getLine)

이게 나오는데 <$>는 좌변의 함수(a -> b)를 우변의 t a에 적용하여 t b 타입을 만들어주는 (여기서 t 는 applicative) 연산자이다. 즉 좌변의 함수를 Applicative 문맥으로 감싸고 이를 다시 Applicative 문맥에 들어있는 값에 적용하게 해준다. (인자가 2개 이상이면 <*> 연산자를 이용해서 언커리할 수 있다.)

여기서 왼쪽의 함수는 String -> Int가 되고, 우변의 getLineIO String이므로 이 함수 전체의 타입은 Int -> IO Int가 된다.

결국 forM 함수를 이용해서 처리한 결과는 IO [Int]가 되고 이는 (<$>) sum에 의해서 IO Int로 귀결된다.

원본

기본으로 주어지는 템플릿은 다음과 같은 식으로 표현하고 있다. (processLine은 제외) IO 와 관련하여 입력받은 값을 처리하는데 있어서 Applicative의 활용이 얼마나 중요한지를 보여주는 좋은 예라 하겠다.

import Control.Applicative
import Control.Monad
import System.IO


main :: IO ()
main = do
  n_temp <- getLine
  let n = read n_temp :: Int     -- 이 두 라인은 n <- readLn :: IO Int 로 대체할 수 있다.
  a_temp <- getMultipleLines n
  let a = map ( map ( read :: String -> Int ) . words ) a_temp

getMultipleLines :: Int -> IO [String]

getMultipleLines n
  | n <= 0 = return []
  | otherwise = do          
      x <- getLine         
      xs <- getMultipleLines (n-1)    
      let ret = (x:xs)    
      return ret