project euler

프로젝트 오일러 042

삼각단어 찾기

sooop

sooop

— 4 min read
프로젝트 오일러 042
Photo by Shubham Dhage / Unsplash

삼각 단어 판정하기

삼각수를 만드는 공식은 n(n+ 1) / 2 입니다. 반대로 어떤 수가 삼각수인지 판정하는 방법은 이 식을 뒤집어서 n에 관한 식으로 만든 후, n이 자연수인지를 검사하면 됩니다.

k = (n2 + n + 1/4 - 1/4) / 2
2k = (n + 1/2)2 - 1/4
(n + 1/2) = sqrt(2k + 1/4)
n = sqrt(2k + 1/4) - 1/2 
def is_triangular(k: int) -> bool:
    n = (2 * k + 0.25) ** 0.5 - 0.5
    return int(n) == n

하지만 우리는 실제 문제 풀이에서는 좀 덜 성가시고 더 빠른 방법을 사용할 거예요.

단어 데이터살피기

문제 페이지에서 단어 데이터 파일의 링크를 클릭해보면 여러 단어가 보입니다. (의외로 양은 많지 않아보입니다.) 모든 단어는 대문자로 이루어져있고, 겹따옴표가 앞뒤에 붙어있습니다. 그리고 각각의 단어는 콤마로 연결됩니다. 따라서 콤마를 기준으로 전체 문자열을 단어로 분리한 후, 각 단어의 앞뒤 따옴표를 제거하여 순수한 단어를 얻을 수 있습니다.

하지만 이런 전처리는 오히려 isalpha() 같은 메소드를 사용해서 알파벳이 아닌 경우 0점으로 계산해도 무방합니다.

삼각수인지 판단하는 다른 방법

문제에서 주어진 데이터의 형식에 대해서는 설명하지 않기 때문에, 문제를 푸는 과정에서 데이터 형식은 필수적으로 확인해야 합니다. 텍스트 파일의 링크를 클릭해서 열어보면 문제에서 제시하는 데이터는 대문자로 쓰여진 일반적인 영어 단어들이라는 것을 알 수 있습니다.

A=1, Z=26이므로 간단하게 25라고 가정하면 "YYYY....Y"로 100자 정도 쓰면 2500점 정도가 나올 것 같습니다. 이것보다 더 큰 삼각수를 '일반적인 영어단어'를 통해서 만들 수 있기는 어려울 것 같습니다. 그러면 넉넉히 500개 정도의 삼각수를 미리 만들어 놓고 멤버십 테스트를 통해서 찾아보는 것이 가장 빠를 것입니다.

이런 내용을 바탕으로 작성한 코드는 다음과 같습니다. 

from urllib.request import urlopen

def main():
    tn = set(n * (n + 1) // 2 for n in range(1, 100))
    url = "https://euler.synap.co.kr/files/words.txt"
    data = urlopen(url).read().decode('utf8')
    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
    return res

if __name__ == '__main__':
    print(main()

보너스

네트워크를 통해서 데이터를 읽어오는 김에, 콤마 단위로 데이터를 끊어서 반환하는 제너레이터를 사용하면 split() 을 사용하지 않아도 됩니다. 다행히 이 문제에서는 단어 파일의 크기가 아주 크지는 않았지만, 단어 파일이 굉장히 크다면 아래와 같은 식으로 파일의 일부부만 로드해서 단어별로 조회하는 기능이 필요할지도 모릅니다. 

from urllib.request import urlopen


def words():
    url = 'https://euler.synap.co.kr/files/words.txt'
    delimiter = ','.encode()
    dellen = len(delimiter)
    res = urlopen(url)
    buffer = bytearray()
    bufsize = 1024
    while True:
        chunk = res.read(bufsize)
        if not chunk:
            yield buffer.decode()
            return
        buffer.extend(chunk)
        while True:
            try:
                idx = buffer.index(delimiter)
                yield buffer[:idx].decode()
                buffer[:idx+dellen] = []
            except ValueError:
                break

def main():
    res = 0
    tns = set(n * (n + 1) // 2 for n in range(1, 5000))
    for w in words():
        score = sum(ord(c) - 64 for c in w if c.isalpha())
        if score in tns:
            res += 1
    return res


if __name__ == '__main__':
    print(main())

Read more