파이썬_실전 프로젝트

프로젝트 오일러 11번문제 - 연속한 4개의 숫자의 곱

20x20의 숫자 배열에서, 가로,세로,대각선 방향으로 연속한 4개의 수를 곱해서 나오는 수중에서 가장 큰수를 찾는 문제입니다.

 

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

 

1. 데이터를 배열또는 2차원 리스트로 읽어와서, (파일 읽어오기 참조)

2. 루프문을 돌면서, 가로,세로,대각선(↘),대각선 (↙) 을 각각 체크해야겠네요.

 

데이터 읽어오기 -1

여러줄의 데이터는 따옴표 3개를 써서 변수로 바로 읽어올수 있습니다.

data='''08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48'''
print(data)
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
....

 

그리고 실제 변수에는

data
'08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n52 70 95 23 04 

줄바꿈 문자가 라인 오른쪽끝마다 들어가있습니다.

 

8번문제에서는 하나의 긴 문자열이 필요해서 \n을 없애주기만 했는데, 이번 문제에서는 2차원 배열형태가 필요하므로,  \n을 기준으로 라인단위로 일단 잘라주겠습니다.

data = data.split('\n')
print(data)
['08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08', '49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00', '81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65', '52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91', '22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80',

 

일단은 1차원 list가 생성이 되었습니다. 이걸 다시 공백을 기준으로 잘라서 2차원 리스트로 만들어 주겠습니다.

numbers=[]
for i in data:
    numbers.append(i.split(' '))
print(numbers)
[['08', '02', '22', '97', '38', '15', '00', '40', '00', '75', '04', '05', '07', '78', '52', '12', '50', '77', '91', '08'], ['49', '49', '99', '40', '17', '81', '18', '57', '60', '87', '17', '40', '98', '43', '69', '48', '04', '56', '62', '00'], ['81', '49', '31', '73', '55', '79', '14', '29', '93', '71', '40', '67', '53', '88', '30', '03', '49', '13', '36', '65'], ['52', '70', '95', '23', '04', '60', '11', '42', '69', '24', '68', '

네 이제 2차원 리스트가 만들어졌으니 문제를 풀수가 있겠네요.

 

데이터 읽어오기 -2

 아니면 문제의 숫자배열을 텍스트 파일에 저장한후에 읽어올수도 있습니다.

filename = 'q011_data.txt'
with open(filename) as file_object:
    lines = file_object.readlines()
len(lines)

 20

파일을 라인단위로 읽으면, 앞에서 \n 을 기준으로 자른것과 마찬가지로 줄단위의 1차원 리스트가 생성이 되고, 이후는 앞의 과정과 같습니다.

numbers=[]
for line in lines:
    numbers.append(line.split())

lines 리스트를 다시 split을 해서 numbers라는 2차원 리스트로 할당해주겠습니다. 이렇게 하면 numbers[i][j] 형식으로 각 데이터를 숫자단위로 불러서 쓸수 있습니다.

 

숫자 4개씩 뽑아내기
H = numbers[0][0:4]
print("H:",H)
H: 08022297

가로방향숫자4개는 간단하게 numbers[0][0:4] 라고 해주면, numbers 리스트의 0번째 하위 list에서 다시 0:4 즉 0,1,2,3의 item을 별도의 H 리스트에 저장하라는 명령이 됩니다.

세로 방향 숫자4개는 같은 하위 리스트의 item들이 아니기때문에, 하위리스트들을 순환하면서 값을 얻어내야 합니다.

V = [numbers[0+k][0] for k in range(0,4)]

원래는 루프문인데, 풀어쓰면 아래와 같습니다.

V=[]
for k in range(0,4):
    V.append(numbers[0+k][0])
print("V:",V)

 각 하위리스트의 0번째 아이템만 모아서 다시 리스트를 만들라는 명령입니다.

대각선 방향들도 세로방향의 식을 살짝 변형하면 쉽게 만들수 있습니다.

D1 = [numbers[0+k][0+k] for k in range(0,4)]
D2 = [numbers[0+k][3-k] for k in range(0,4)]

 

반복문 만들기
for i in range(17):
    for j in range(17):
        H = numbers[i][j:j+4]
        V = [numbers[i+k][j] for k in range(0,4)]
        D1 = [numbers[i+k][j+k] for k in range(0,4)]
        D2 = [numbers[i+k][j+3-k] for k in range(0,4)]
        print("H:",H)
        print("V:",V)
        print("D1:",D1)
        print("D2:",D2)

전체 배열은 20x20 이고, 우리가 계산에 필요한 크기는 4X4이기 때문에, 마지막에 불러와야될 루프는 16,17,18,19(인덱스값)가 되야 합니다. 그래서 range에 17을 주게되면, 루프는 16을 끝으로 종료됩니다.

그리고 변수i,j를 각각 number의 첫번째 인덱스와, 두번째 인덱스에 더해주기만 하면 됩니다.

 

계산

 만약 합계를 계산하고 싶다면, 위 식들을 그대로 sum() 함수에다가 넣어주면 됩니다. 아 그전에 숫자들이 현재 문자형태로 저장되어 있으므로 int()로 숫자로 바꿔줘야 됩니다.

for i in range(17):
    for j in range(17):
        H = sum([int(k) for k in numbers[i][j:j+4]])
        V = sum([int(numbers[i+k][j]) for k in range(0,4)])
        D1 = sum([int(numbers[i+k][j+k]) for k in range(0,4)])
        D2 = sum([int(numbers[i+k][j+3-k]) for k in range(0,4)])
        print("H:",H)
        print("V:",V)
        print("D1:",D1)
        print("D2:",D2)

그런데 문제에서는 곱셈을 계산해야 합니다. 곱셈은 불행(?)하게도 sum()같은 간단한 함수가 없습니다. 그래서 만들어 쓰기로 하죠.

from functools import reduce

def prod(t):
    return reduce(lambda x, y: x*y, t)

함수는 위와 같습니다. 매개변수(t)로 배열을 받으면, 그 안의 모든 item들을 다 곱해서 반환하라는 명령입니다. 첫줄은 reduce함수를 사용하기 위해서 functools라는 모듈을 불러온거구요, 그러면 이제 prod()를 sum()처럼 사용할수 있습니다. (product:곱셈)

from functools import reduce

def prod(t):
    return reduce(lambda x, y: x*y, t)

for i in range(17):
    for j in range(17):
        H = prod([int(k) for k in numbers[i][j:j+4]])
        V = prod([int(numbers[i+k][j]) for k in range(0,4)])
        D1 = prod([int(numbers[i+k][j+k]) for k in range(0,4)])
        D2 = prod([int(numbers[i+k][j+3-k]) for k in range(0,4)])
        print("H:",H)
        print("V:",V)
        print("D1:",D1)
        print("D2:",D2)

H: 34144
V: 1651104
D1: 279496
D2: 24468444
H: 162184
V: 336140
D1: 57816
...

 

결과값 저장

이제 최대값을 찾아야 되는데, 리스트를 max() 함수에다 넣어서 max(리스트) 를 해주게 되면, 최대값을 쉽게 찾을 수 있습니다. 그러면 모든 결과값들을 result 라는 이름의 리스트에다가 저장해주기로 하죠.

from functools import reduce

def prod(t):
    return reduce(lambda x, y: x*y, t)

result=[]
for i in range(17):
    for j in range(17):
        result.append(prod([int(k) for k in numbers[i][j:j+4]]))
        result.append(prod([int(numbers[i+k][j]) for k in range(0,4)]))
        result.append(prod([int(numbers[i+k][j+k]) for k in range(0,4)]))
        result.append(prod([int(numbers[i+k][j+3-k]) for k in range(0,4)]))
max(result)
70600674

 for문 앞에 result=[]으로 빈 리스트를 만들어주고, 각 계산값을을 .append() 명령으로 리스트에다가 추가해줍니다. 그리고 마지막에  결과값을 출력해주면 됩니다.

 

참고

곱셈 함수는 다른방법으로도 만들수 있습니다.

from functools import reduce
import operator
def prod(t):
    return reduce(operator.mul, t, 1)

아니면 함수없이 각각 라인에다가 직접작성해줘도 됩니다.

D2 = reduce(lambda x, y: x*y,[int(numbers[i+k][j+3-k]) for k in range(0,4)])

 

댓글

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