Purple Haskell (1)

https://codeforces.com/profile/haskell_brooks_curry

이 계정도 퍼플 찍는 거 목표로 슬슬 연습해야 할 것 같아서 풀기 시작.

하스켈은 문제 푸는 기본 템플릿 형태를 어떻게 해야하나 고민을 좀 많이 했는데 일단 아래와 같은 방식으로 정했다. input - output - solve 세 가지를 구현하는 형태인데 이게 그나마 젤 편한 듯. solve가 튜플을 인자로 받아야하는게 쪼끔 불만이긴 한데 더 나은 방법을 잘 모르겠다.

	{-# LANGUAGE BangPatterns #-}
	import System.IO
	import Control.Applicative
	import Control.Monad
	import Data.Char
	import Data.List
	import Data.Maybe
	import Data.Monoid
	import Data.Function (fix)
	import Data.Array (Array, array, (!))
	import Data.ByteString.Lazy.Builder
	import Data.ByteString.Lazy.Builder.ASCII
	import qualified Data.Map as Map
	import qualified Data.ByteString as BS
	import qualified Data.ByteString.Char8 as BS8
	construct :: (BS.ByteString -> Maybe (a, BS.ByteString)) -> BS.ByteString -> [a]
	construct reader str
	| BS.null str = []
	| isSpace (BS8.head str) = construct reader (BS8.tail str)
	| otherwise = let Just (i, other) = reader str in i : construct reader other
	getInts :: IO [Int]
	getInts = construct BS8.readInt <$> BS.getLine
	getIntegers :: IO [Integer]
	getIntegers = construct BS8.readInteger <$> BS.getLine
	printInts :: [Int] -> IO ()
	printInts = putStrLn . intercalate " " . map show
	main = input >>= output . solve
	input =
	solve =
	output =

view raw default.hs hosted with ❤ by GitHub

일단 이대로 쓰고 더 나은 방법 생각나면 고치자

 

https://codeforces.com/group/DEuKcKDfls/contest/227543

주말 스터디에서 진행했던 셋을 갖고 연습을 하기로 했다. 일단 먼 옛날에 했던 1라운드 문제부터 하스켈로 짜기. D번이 DP인데 DP를 어떻게 해야 하스켈로 잘 짤 수 있는지 아직 잘 모르겠어서 일단 패스. DP랑 다차원 배열, tree, graph 같은 애들이 항상 골치를 썩이는데 여전히 어떻게 해야할지 잘 모르겠음. array 이런 거 안 쓰고 하고 싶은데 방법이 없나

 

input - output 부분 코드는 별로 중요하지 않으니 각 문제별 solve 부분 코드만 올려둔다.

 

A. Polycarp's Pockets

solve = maximum . map length . group . sort

view raw A.hs hosted with ❤ by GitHub

n개의 주어진 숫자 중에 개수 제일 많은 걸 출력하는 문제. 정렬 -> group -> length -> maximum 그냥 그대로 짜면 직관적임

B. Mishka and Contest

	solve (n, k, arr) = n - length (remove k $ reverse $ remove k arr)
	where remove k = dropWhile (\x -> x <= k)

view raw B.hs hosted with ❤ by GitHub

배열의 왼쪽 끝에서부터 k 보다 큰 수 나올 때까지 원소 전부 제거, 오른쪽 끝도 마찬가지 방식으로 제거한 다음 제거된 원소 수를 찍는 문제다.

dropWhile을 쓰면 왼쪽 끝에서 지우는 건 할 수 있고, 오른쪽 끝에서 지우는건 왼쪽 끝에서 조건에 맞게 지운 후 배열을 뒤집고 오른쪽 끝에서 동일한 동작을 수행하면 된다. 그 다음 n에서 남은 원소 개수 빼주면 끝.

C. Puzzles

	solve (n, m, arr) = minimum $ map (\(a, b) -> b - a) $ zip sorted (drop (n-1) sorted)
	where sorted = sort arr

view raw C.hs hosted with ❤ by GitHub

배열에서 n개 원소를 골랐을 때, 그 n개 원소 내에서 최솟값과 최댓값의 차이를 최소로 만드는 문제다. 일단 정렬하고 보면 정렬한 배열에서 연속한 n개를 뽑는게 최선이다. 그러니 정렬하고 정렬한 결과에서 n-1칸 인덱스 차이나는 두 값 차이중 젤 작은 걸 리턴해주면 답이 된다.

 

하스켈로 풀 때마다 느끼는데 어느정도 쉬운 문제는 하스켈로 짜는게 훨씬 간결하고 코딩량이 압도적으로 적다(실수도 덜하고). 근데 아직 내가 하스켈로 문제 푸는게 C++로 문제 푸는 거만큼 안 익숙해서 아직은 C++로 문제 푸는게 더 빠르긴 함. 쉬운거도 많이 풀면서 익숙해질 필요가 있는 듯.

 

그리고 하스켈로는 도저히 풀지를 못하는 문제들이 좀 있는데(맨 처음 언급한 것들), 이런 것들 좀 깔끔하게 쉽게 잘 푸는 방법을 연구하면 하스켈로도 퍼플 찍을 수 있을 것 같다. 문제 해결 능력이 부족한 건 아니니까..