파이썬(Python) 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수

안녕하세요, 츄르 사려고 코딩하는 집사!      코집사입니다.

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

이번 글은 프로젝트 오일러에서 제공되는 문제 Problem 4 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수입니다.

1. 문제

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

 

2. 코드

import time
start = time.time() #시간 측정을 위한 변수
A = [] #결과 값을 저장하여 최대값을 출력하기 위한 리스트
for i in range(400,1000): #100에서 300까지의 곱셈은 5자리가 나오기 때문에 400부터 시작
    for j in range(400,1000):
        list = str(i*j) #글자를 비교하기 위해 문자열로 저장
        if list[0] == list[5] and list[1] == list[4] and list[2] == list[3]:
            A.append(int(list))
print(max(A))
print(time.time() - start)
            

3. 답

906609

 

4. 풀이

1) 문제를 읽어보면 세자리수의 곱의 가장 큰 대칭수를 구하는 문제이므로, 세자리 수의 곱 결과를 생각해봅니다. 

2) 예를 들어, 100X100 = 10000, 200X200 = 40000, 300X300 = 90000, 400X400 = 160000이런식으로 진행이 된다. 정확하게 317X317을 했을 때 결과값이 6자리 결과가 나온다.

3) 세자리 수 곱하기 중 가장 큰 대칭수를 구하기 위해서는 적어도 큰 세 자리 수의 곱연산을 해야 나온다는 것을 알 수 있다.

4) 나는 대충 어림잡아 400부터 반복문을 돌렸다.

5) 그럼 결과값은 6자리의 결과이므로, 이 6자리 결과 값을 각 문자열의 위치에서 비교하기 위해 string 형으로 저장을 하여 비교를 한다.

6) if문을 사용하여 0번과 5번, 1번과 4번, 2번과 3번이 같으면 곱한 값을 새로운 리스트 A에 저장을 한다.

7) 리스트 A에서 가장 큰 값을 출력하면 된다.

8) 이 방법은 정석적인 방법이 아니다. 그저 생각의 흐름대로 풀었기에 다른 자리수가 나오면 제대로 맞출 수가 없다.

5. 다른 풀이법(정석)

1) 코드

import time
start = time.time()
A = []
for i in range(100,1000):
    for j in range(100,1000):
        list = str(i*j)
        for k in range(len(list)):
            if list[k] != list[-(k+1)]:
                break
        else:
            A.append(int(list))
print(max(A))
print(time.time() - start)

 

2) 풀이

i. 이 방법은 자리수에 상관없이 적용될 수 있는 방법이다.

ii. list에 입력하는 방법은 같다. 이제 자리수를 비교하는 방법이 다르다.

iii. list에서 0번째 자리와 맨 마지막 자리를 비교를 해야 한다. 비교를 하기 위해서는 리스트에서 맨 마지막 자리는 -1로 표현을 할 수 있다.

iV. 예를 들어, list에 101이라는 string형이 들어있다면, list[0]은 1, list[-1]은 1이 된다.

아래의 그림처럼 된다.

V. 그렇기에, list의 크기만큼 for문을 돌려 각 자리수를 비교하면 대칭수를 판별할 수 있다.

 

3) 결과