Data.List와 Data.Array 사이의 변환

문제: https://www.hackerrank.com/challenges/matrix-rotation

난이도 Hard이지만 코드포스로 따지면 Div2 B 정도 되는 문제다. m×n 배열을 바깥 테두리부터 한 층씩 잘라내어 각각 r번 돌리고 다시 합쳐서 출력하면 된다. 이 때 r이 너무 크니 r을 테두리 길이로 나눈 나머지 만큼만 돌린다.

절차형 언어면 그냥 배열을 직접 조작해서 풀었는데 하스켈이니 리스트와 배열을 왔다갔다 하면서 풀어야 한다. mutable array를 사용하면 하스켈을 쓰는 의미가 퇴색되니 쓰지 않는다.

먼저 입력을 받는다. 배열 원소가 최대 90000개여서 String으로 읽으면 I/O 하다 시간 초과가 날 것 같으니 ByteString으로 읽는다.

import Control.Monad

import Data.Array

import Data.Maybe

import qualified Data.ByteString.Char8 as BS8

readInt = read `fmap` getLine :: IO Int

readInts = (map parseInt . BS8.words) `fmap` BS8.getLine :: IO [Int]

parseInt = fst . fromJust . BS8.readInt

main = do

    [m,n,r] <- readInts

    rows <- replicateM m readInts :: IO [[Int]]

입력은 rows에 리스트의 리스트 형태로 바인딩된 상태다. 이걸 레이어 별로 분리해야 하는데 리스트의 임의 접근은 O(n)으로 개느리기 때문에 일단 배열로 변환한다.

...

main = do

    [m,n,r] <- readInts

    rows <- replicateM m readInts :: IO [[Int]]

    let ary = array ((1,1),(m,n)) [((i,j),x) | (i,xs) <- zip [1..m] rows, (j,x) <- zip [1..n] xs]

    let numLayers = (min m n) `div` 2

    let lengths = map (\i -> 2 * (m + n - 2) - (i * 8)) [0 .. numLayers-1]

    let offsets = map (r `mod`) lengths

배열을 다시 레이어 별로 쪼개서 레이어의 리스트로 만든다.

type Layers = [[Int]]

toLayers :: Array (Int,Int) Int -> Layers

toLayers ary = map makeLayer [1..numLayers] where

    (_,(m,n)) = bounds ary

    numLayers = (min m n) `div` 2

    makeLayer layer = [ary ! ix | ix <- layerIndices m n layer]

layerIndices :: Int -> Int -> Int -> [(Int,Int)]

layerIndices m n k = [(i,k) | i <- [k .. m-k+1]]

    ++ [(m-k+1,j) | j <- [k+1 .. n-k+1]]

    ++ [(i, n-k+1) | i <- [m-k,m-k-1 .. k]]

    ++ [(k,j) | j <- [n-k,n-k-1 .. k+1]]

레이어 별로 r번 회전시키는 것은 간단하다. 단순히 리스트 맨 뒤에서 필요한 만큼 잘라내어 앞에 가져온다.

rotate :: Layers -> [Int] -> [Int] -> Layers

rotate layers offsets lengths = map f (zip3 layers offsets lengths) where

    f (layer, offset, len) = drop (len - offset) layer ++ take (len - offset) layer

회전이 끝난 레이어의 리스트를 다시 배열로 변환하고 출력하면 끝난다.

main = do

    [m,n,r] <- readInts

    rows <- replicateM m readInts :: IO [[Int]]

    let ary = array ((1,1),(m,n)) [((i,j),x) | (i,xs) <- zip [1..m] rows, (j,x) <- zip [1..n] xs]

    let numLayers = (min m n) `div` 2

    let lengths = map (\i -> 2 * (m + n - 2) - (i * 8)) [0 .. numLayers-1]

    let offsets = map (r `mod`) lengths

    let layers = toLayers ary

    let answer = toArray (rotate layers offsets lengths) m n

    forM [1..m] $ \i -> do

        forM [1..n] $ \j -> do

            putStr $ show (answer ! (i,j))

            putChar ' '

        putStrLn ""

    putStrLn ""

toArray :: Layers -> Int -> Int -> Array (Int,Int) Int

toArray layers m n = array ((1,1),(m,n)) src where

    numLayers = (min m n) `div` 2

    src = concat (map makeLayer (zip [1..numLayers] layers))

    makeLayer (k,layer) = zip (layerIndices m n k) layer

해커랭크는 통과 유무만 알려줄 뿐 메모리 사용량과 걸린 시간을 보여주지 않아서 얼마나 효율적인 지는 모르겠다. 테스트케이스 받아다가 직접 측정하기도 귀찮고 -_- 일단 통과는 하는 코드.