원소를 등장횟수기준으로 필터링하기

filter-element-faster.hs

import Control.Monad
import Data.List
import Data.Function

process :: Int -> [Int] -> [Int]
process k ns =
  let indexed = zip ns [1..]
      sorted = sortBy (compare `on` fst) indexed
      grouped = groupBy ((==) `on` fst) sorted
      filtered = filter ((>= k) . length) grouped
  in map fst . sortBy (compare `on` snd) . map head $ filtered
  
main :: IO ()
main = 
  let readInts = (map (read:: String -> Int) . words) <$> getLine
  in do
    n <- readLn :: IO Int
    forM_ [1..n] $ \_-> do
      (_:k:_) <- readInts
      lst     <- readInts
      result  = process k lst
      if null result then do putStrLn "-1"
                     else do putStrLn . unwords . map show $ result

filter-element.hs

import Control.Monad
import Data.List

{- 정수 리스트 L과 정수 n이 주어졌을 때,
 - 리스트 L의  원소중에서 n 번 이상 등장한 원소들을
 - 등장순서대로 필터링하여 표시하라
 -}

 -- CountedList를 만들자
data CountedList a = Node a Int (CountedList a)| 
                     Nil 
                     deriving (Show)

-- 새 값을 추가한다.
-- 빈 리스트라면 노드로 카운트 1인 노드로 변환되고
-- 같은 값이 있는 노드라면 카운트가 올라가며
-- 그렇지 않으면 뒤의 꼬리에 추가하는 식으로 처리한다.
append :: (Eq a) => CountedList a -> a -> CountedList a
append Nil newValue = Node newValue 1 Nil
append (Node val cnt next) newValue
      | val == newValue = Node val (cnt+1) next
      | otherwise       = Node val cnt (append next newValue)

-- append를 재귀적용하여 리스트 -> 카운트리스트로 변환할 수 있다.
build :: (Eq a) => [a] -> CountedList a
build = foldl' append  Nil

filteredList :: Int -> CountedList a -> [a]
filteredList _  Nil = []
filteredList k (Node val cnt next) = 
    if k > cnt then filteredList k next
               else val:(filteredList k next)

main =
    let getInts = (map (read :: String -> Int ) . words) <$> getLine
    in do
    n <- readLn :: IO Int
    forM_ [1..n] $ \_ -> do
        (_:k:_) <- getInts
        lst <- getInts
        let result = filteredList k . build $ lst
        if null result then do putStrLn "-1"
                       else do putStrLn . unwords . map show $ result