문제
다음은 연속된 1000자리 숫자입니다. (읽기좋게 50자리씩 잘라놓음)
73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450
여기서 빨간색으로 표시된 71112의 경우 7,1,1,1,2를 모두 곱하면 14가 됩니다.이런식으로 맨처음 (7 * 3 * 1 * 6 * 7 = 882)부터 맨 끝 (6 * 3 * 4 * 5 * 0 = 0)까지 5자리의 숫자들의 곱을 구할 수 있습니다. 이렇게 구할 수 있는 숫자의 곱 중에서 가장 큰 값은 얼마입니까?
풀이
제시된 데이터를 파싱해서 1자리 정수의 배열로 만들었다고 가정하자. 그러면 1번째 자리부터 996번째자리까지 반복하면서 그 자리에서부터 5개씩 숫자를 골라서 그 곱을 계산하고 그 중 최대값을 찾으면 된다.
배열로 만들어진 데이터를 data라 가정하면 i 번째 자리에서 5개의 숫자를 골라내면 data[i:i+4] 가 된다. 배열의 곱은 prod() 함수로 구할 수 있기에 prod(data[i:i+4])로 만들 수 있다. 이 계산식을 1:996의 범위에 맵핑하고 최대값을 찾으면 되겠다.
문자열의 각 자리를 정수로 만들기
숫자를 표현하는 문자열의 각 글자를 정수로 만드는 방법에는 여러 가지가 있을 수 있는데, 그 중 두 가지 정도를 알아보자.
먼저 parse() 함수를 이용하는 것이다. 이 함수는 숫자 리터럴을 표현하는 문자열을 특정한 타입의 숫자값(정수 혹은 실수)으로 변환한다. 예를 들어 "123"이라는 문자열이 있을 때, parse(Int, "123")이라고 하면 그 문자열을 정수 123으로 변환해준다. 만약 "123"의 각 자리수를 정수로 변환하고 싶다면, "123"을 각 글자로 쪼개어 이를 적용한다.
문자열을 각 글자로 쪼개는 방법은 split() 함수를 사용하며, 쪼개는 기준을 "" 빈문자열을 쓰는 것이다.
nums = map(x -> parse(Int, x), split("123", ""))
이 때, parse는 broadcasting을 사용하여 다음과 같이 보다 간단히 표현할 수도 있다.
nums = parse.(Int, split("123", ""))
특정 처리를 하는 함수 뒤에 . 을 붙이고 단일 타입인자 대신에 배열을 받으면 해당 배열의 각 원소로 함수의 연산이 broadcast된다.
다른 한가지의 방법은 ASCII 코드 내에서 숫자들이 크기 순으로 나란히 들어있음을 이용하는 것이다. '0'의 코드 값은 48이다. 개별 글자(Char 타입)를 Int() 함수에 넣으면 그 글자의 코드값이 나온다. 따라서 이렇게 나온 코드 값에서 48을 빼면 그 숫자의 값과 일치하게 된다.
그런데 문제에서 제시하는 문자열에는 개행문자(줄바꿈)가 포함이 되어 있다. 개행문자는 parse()도, Int()도 제대로 처리하지 못하기 때문에 개행을 없애야한다.
s = .... # 여러 줄의 숫자문자열
replace!(s, "\n"=>"") # 개행 제거
data = parse.(Int, split(s, ""))
이렇게 replace로 처리할 수 있으며, 다음과 같이 매 문자를 처리할 때에는 해당 문자가 숫자인지 아닌지로 필터링할 수 있다.
s = ...
data = [Int(c) - 48 for c in s if isdigit(c)]
어떤 방법을 쓰든 data는 같은 결과를 얻게 될 것이다. 힌트를 주자면 두 번째 방법이 조금 더 빠를 것이다. 왜냐하면 split()은 하나의 문자열을 여러 문자열의 배열로 변환하기 때문에 1000개의 문자열 객체가 생성되는 비용이 들어갈 것이기 때문이다.
배열의 최대값을 구하는 함수는 maximum이다. max의 경우에는 두 개의 인자 중에서 큰 값을 리턴한다.
해답
@time let s = """73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"""
data = [Int(c)-48 for c in s if isdigit(c)]
[prod(data[i:i+4]) for i=1:996] |> maximum |> println
end