Project Euler

프로젝트 오일러 042

프로젝트 오일러 42번, 단어 파일에서 '삼각 단어'의 개수를 찾는 문제입니다. 단어 값을 계산하고, 그 값이 삼각수인지 판별하는 방법을 설명합니다. 단어 파일을 읽어 단어 값을 계산하고 삼각수 여부를 확인하는 파이썬 풀이를 제시합니다.

2분
#project euler #python

삼각 단어 판정하기

n번째 삼각수를 만드는 공식은 n(n+1)÷2이고, 이를 뒤집으면 어떤 수가 n번째 삼각수인지를 판정하는 식을 만들 수 있습니다.

이 때 n이 자연수로 떨어진다면 k가 삼각수가 됩니다.

def is_triangular(k: int) -> bool:
    n = (2 * k + 0.25) ** 0.5 - 0.5
    return int(n) == n

하지만 다른 방법도 있습니다.

단어 데이터살피기

파일로 주어진 데이터를 처리해야하기 때문에, 일단은 데이터를 먼저 살펴보는 것이 필요합니다. 각 단어는 줄 단위로 주어지는지, 제거해야 하는 문자가 있는지 등등을 살펴봐야하기 때문이죠.

파일을 다운로드 받아 열어보면 (혹은 링크를 클릭해서 브라우저에서 열어보면) 대문자로된 단어들이 따옴표로 둘러싸여있고, 각 단어는 콤마로 구분된다는 것을 알 수 있습니다. 그리고 각 단어들은 그렇게 심각하게 긴 단어는 보이지 않습니다. 따라서 단어의 최대 길이를 50정도로 잡는다고 해도 각 단어의 점수는 1500을 넘기지 않을 것입니다. 따라서 100개 정도의 삼각수 집합을 만들어 놓고 여기에 있는지를 보는 것이 더 빠르고 간편할 수 있습니다.

참고로 각 단어의 점수를 계산할 때에는, ord() 함수를 쓸 수 있는데, 대문자 A의 아스키코드값이 65이므로, ord(c) - 64를 합산하면 단어의 점수가 구해집니다.

import request

def main():
    tn = set(n * (n + 1) // 2 for n in range(1, 100))
    data = request.get('https://euler.synap.co.kr/files/words.txt').text
    res = 0
    for word in data.split(','):
        score = sum(ord(c) - 64 for c in word if c.isalpha())
        if score in tn:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

보너스

데이터를 미리 살펴보는 것은 매우 중요합니다. 텍스트 파일은 그 자체로 크기에 제한이 없기 때문에 용량이 수백메가 혹은 수 기가에 달할 수 있습니다. request.get().text는 응답을 모두 읽어서 메모리에 적재하기 때문에 데이터가 엄청나게 크다면 메모리 부족으로 프로그램이 죽게 됩니다. 따라서 이런 경우라면 수십~수백kb 단위로 파일을 읽어들여서 처리해야 할 수도 있습니다.

requests를 사용하는 경우, stream=True 옵션으로 연결을 만들고, iter_content()를 사용하여 일정량의 바이트 수만큼씩만 파일을 읽어올 수 있습니다. 이렇게하면 GB 단위의 큰 파일도 문제없이 처리할 수 있습니다.

import requests
from typing import Generator


ks = set(n * (n + 1) // 2 for n in range(1, 50))


def reader(url: str, delimiter:str=',') -> Generator[str, None, None]:
    d = delimiter.encode()
    buffer = bytearray()
    res = requests.get(url, stream=True)
    if res.status_code != 200:
        raise ValueError(f'invalid response: code={res.status_code}')
    for chunk in res.iter_content(chunk_size=1024):
        buffer.extend(chunk)
        while d in buffer:
            yield buffer[:buffer.index(d)].decode('utf-8')
            buffer[:buffer.index(d)+1] = []
    yield buffer.decode()

def main():
    res = 0
    for word in reader('https://euler.synap.co.kr/files/words.txt'):
        score = sum(ord(c) - 64 for c in word if c.isalpha())
        if score in ks:
            res += 1
    print(res)

if __name__ == '__main__':
    main()