프로젝트 오일러 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의 첫번째 인덱스와, 두번째 인덱스에 더해주기만 하면 됩니다.