파이썬으로 수학문제 풀기- 프로젝트 오일러(project euler, 22번부터)

프로젝트 오일러 24번 문제 - Lexicographic permutations

0부터 9까지 10자리의 순열중, 백만번째 수를 구하는 문제입니다.

 

두가지정도로 해결할수 있는데, 첫번째는 직관적으로 숫자를 한자리씩 올려가며 100만번까지 순열을 만들어 내면서 계산하는 방법이고, 두번째는 진법 변환하듯이 각자릿수의 크기로 나누어서 구하는 방법입니다. 두번째 방법으로 하면 굳이 프로그래밍을 하지 않아도 될것 같네요. 일단 첫번째 방법만 해보도록 하겠습니다.

 

 

루프문 만들기

첫번째 수인 0123456789 부터 백만까지 루프문을 만듭니다. range에는 100만이 포함이 안되서, 실제로는 999,999 개이지만, 시작하는 숫자가 첫번째이기 때문에, 출력결과는 100만번째수가 맞습니다.

def get_next_permutation(string):
    #code here
    return number
    
string='0123456789'
for i in range(1,1000000):    
    string = get_next_permutation(string)
print(string)

 

함수부분

함수를 만들기 전에 순열의 패턴을 보면,

0123456789

0123456798

0123456879

0123456897

0123456978

0123456987

...

마지막 숫자 다음에 올숫자는

0123457689 입니다.  위 마지막숫자에서 끝세자리 987은 이미 최대로 자리가 올라가 있으므로, 그앞에 있는 6이 숫자가 올라가야 되고, 새로운 수는 오른쪽에 있는 수 중에서 그다음으로 큰수인 7입니다.(오른쪽에 7이 없으면 8이나 9가 될수도 있습니다.)

7을 6자리에 넣고, 남은 698 을 오름차순으로 정렬해서 689를 만들어서 뒷부분에 붙입니다.

이것을 코드로 표현하면 아래와 같습니다.

def get_next_permutation(string):
    i=len(string)-2
    while i >= 0:
        if string[i] < string[i+1]:
            target = sorted(string[i:])
            new_num = target.pop(target.index(string[i])+1)
            last_nums = ''.join(target)
            return string[:i] + new_num + last_nums
        i-=1

string[i]가 6이되고, string[i:] = '6987'이 되고, sorted()로 정렬을 하면, ['6','7','8','9']의 리스트가 생성이 되서, target에 저장이 됩니다. 그리고 target에서 6 의 위치(index)를 계산하고, 1을 더하면, 7의 위치가 나오고, 그 7을 target.pop(index) 로 뽑아내서 new_num 에 저장을 합니다. 이때 pop 을 하면, 뽑아내고 남은 target에서는 7이 삭제가 되서, 자동으로 ['6','8','9'] 만 남아서, 마지막 줄에서 ''.join으로 합쳐주기만 하면 됩니다.

 

def get_next_permutation(string):
    i=len(string)-2
    while i >= 0:
        if string[i] < string[i+1]:
            target = sorted(string[i:])
            new_num = target.pop(target.index(string[i])+1)
            last_nums = ''.join(target)
            return string[:i] + new_num + last_nums
        i-=1

string='0123456789'
for i in range(1,1000000):    
    string = get_next_permutation(string)
print(string)

 

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
nomadlife
현재 버전
선택 버전
graphittie 자세히 보기