Project Euler #38 - Pandigital multiples

프로젝트 오일러 38번
192에는 1, 2, 3을 곱하면
192
384
576
1~9가 한번씩 나온다. 이런 성질을 갖는 가장 큰 수는?

9자리 중에 가장 큰 수는 987654321.
9 _ _ _ * 2 = 18 _ _ _ 의 성질을 만족하는 숫자를 찾을 수 있으면 좋겠다.
9, 1, 8을 빼고 남은 숫자는 2, 3, 4, 5, 6, 7
9 a _ _ 에서 a 는 5보다 작아야 하므로 2나 3이 올 수 있다. 4가 오면 *2 했을 때 문제.
그럼 9 3 _ _ * 2 = 1 8 6 _ _ 또는 9 3 _ _ * 2 = 1 8 7 _ _ 의 형태가 될 수 있을까?
남은 숫자가 몇 개 안 되니까 모든 경우를 따져볼 수 있는데.. 932718654 가 답이다.

이번에는 코딩으로 풀어보자.
우선 9, 18, 27, 36, 45는 알려진 후보이므로 이보다 큰 걸 찾는 문제로 생각하면 된다.
첫번째 수가 9로 시작하는 2자리라면, *2=>3자리, *3=>3자리.. 붙여서 9자리를 만들 수 없다.
첫번째 수가 9로 시작하는 3자리라면, *2=>4자리, *3=>4자리.. 붙여서 9자리를 만들 수 없다.

첫번째 수는 9로 시작하는 4자리라야 한다. (이것도 아니라면 답은 918273645)

def pandigital():
    for i in range(9876,9123,-1):
        if set(str(i)+str(i*2)) == set('123456789'):
            return i*100000+i*2
    return 918273645

print pandigital()

끝.