Project Euler Problem 11 : 20×20 격자에서 연속된 네 숫자의 곱 중 최대값

---

Project Euler 문제를 해답을 포스팅합니다.

※ 주의 : 최적화는 할 수 있는 만큼했습니다. 따라서 속도면에서는 많이 부족합니다.

           문제를 푸는데 목표를 두었고 또한 TDD를 최대한 활용하였습니다.

           몇가지 문제의 경우 TDD를 안한 경우도 있습니다.

           혹시, 최적화 또는 속도 증가에 대한 부분을 지적해주실 분은 너무나도 감사합니다.

---

Project Euler Problem 11

아래와 같은 20×20 격자가 있습니다.

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

위에서 대각선 방향으로 연속된 붉은 숫자 네 개의 곱은 26 × 63 × 78 × 14 = 1788696 입니다.

그러면 수평, 수직, 또는 대각선 방향으로 연속된 숫자 네 개의 곱 중 최대값은 얼마입니까?

---

위에서 대각선 방향으로 연속된 붉은 숫자 네 개의 곱은 26 × 63 × 78 × 14 = 1788696 입니다.

그러면 수평, 수직, 또는 대각선 방향으로 연속된 숫자 네 개의 곱 중 최대값은 얼마입니까?

하나의 숫자에 대해서 수평, 수직, 대각선 방향으로 모두 계산을 한다면 총 8가지가 나옵니다.

하지만, 다음 숫자들에 대하여 중복된 연산이 발생합니다.

따라서, 수형, 수직, 대각선(위,아래) 로 한번씩만 계산하여 총 4가지로 줄일 수 있습니다.

배열 넘어가서 계산하는 예외는 귀찮아서 try-catch로 처리하였습니다. 약간의 계산을 통하여 이 구문을 줄 일 수는 있을거같습니다. 또한 메인함수 부분을 정리하고 싶었지만 딱히 이쁜 방법이 안 떠오르네요.

---

Source Code

TestClass Code

public class TestClass { 

     
    @Test 
    public void testCalRow() {
        MaxNumFinder20x20 finder = new MaxNumFinder20x20(); 
         
        long result = finder.calRow(7,7); 
         
        assertEquals(11251800, result); 
    } 
     
    @Test 
    public void testCalCol() {
        MaxNumFinder20x20 finder = new MaxNumFinder20x20(); 
         
        long result = finder.calCol(7,7); 
         
        assertEquals(1532960, result); 
    } 
     
    @Test 
    public void testCalRowCol_Up() {
        MaxNumFinder20x20 finder = new MaxNumFinder20x20(); 
         
        long result = finder.calRowCol_Up(7,7); 
         
        assertEquals(1404000, result); 
    } 
     
    @Test 
    public void testCalRowCol_Down() {
        MaxNumFinder20x20 finder = new MaxNumFinder20x20(); 
         
        long result = finder.calRowCol_Down(7,7); 
         
        assertEquals(261900, result); 
    } 
     
    @Test 
    public void getDataTest() {
        MaxNumFinder20x20 finder = new MaxNumFinder20x20(); 
         
        int [][] data = finder.getData(); 
        assertEquals(8, data[0][0]); 
    } 
     
    @Test 
    public void stringToLongTest() {
        String string1 = "01"; 
        String string2 = "00"; 
         
        int num1 = Integer.parseInt(string1); 
        int num2 = Integer.parseInt(string2); 
         
        assertEquals(1, num1); 
        assertEquals(0, num2); 
    } 
     
    @Test 
    public void inputDataTest() {
        MaxNumFinder20x20 finder = new MaxNumFinder20x20(); 
        finder.inputData("08 02 22"); 
        finder.inputData("08 02 22"); 
         
        ArrayList<Integer> outputData = finder.getDataList(); 
         
        assertEquals((Integer)8, outputData.get(0)); 
    } 
}

Main Class Code

public class Main { 
    public static void main(String [] args) {
        MaxNumFinder20x20 finder = new MaxNumFinder20x20(); 
         
        long maxNum = 0; 
         
        for(int x=0; x<20; x++) { 
            for(int y=0; y<20; y++) { 
                try { 
                    if( maxNum < finder.calRow(x, y) ) { 
                        maxNum = finder.calRow(x, y); 
                    } 
                    if( maxNum < finder.calCol(x, y) ) { 
                        maxNum = finder.calCol(x, y); 
                    } 
                    if( maxNum < finder.calRowCol_Up(x, y) ) { 
                        maxNum = finder.calRowCol_Up(x, y); 
                    } 
                    if( maxNum < finder.calRowCol_Down(x, y) ) { 
                        maxNum = finder.calRowCol_Down(x, y); 
                    } 
                } catch (Exception e) { 
                    continue; 
                } 
            }//end of y 
        }//end of x 
     
        System.out.println("result : " + maxNum); 
    } 
}

MaxNumFinder20x20 Class Code

public class MaxNumFinder20x20 {
     
    ArrayList<Integer> data_List = new ArrayList<Integer>(); 
    int [][] data = new int[20][20]; 
     
    public MaxNumFinder20x20() { 
        this.inputData("08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08"); 
        this.inputData("49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00"); 
        this.inputData("81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65"); 
        this.inputData("52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91"); 
        this.inputData("22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80"); 
        this.inputData("24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50"); 
        this.inputData("32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70"); 
        this.inputData("67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21"); 
        this.inputData("24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72"); 
        this.inputData("21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95"); 
        this.inputData("78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92"); 
        this.inputData("16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57"); 
        this.inputData("86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58"); 
        this.inputData("19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40"); 
        this.inputData("04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66"); 
        this.inputData("88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69"); 
        this.inputData("04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36"); 
        this.inputData("20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16"); 
        this.inputData("20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54"); 
        this.inputData("01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"); 
         
        getData(); 
    } 
     
    public void inputData(String string) {
        String [] datas = string.split(" "); 
        for(int i=0; i<datas.length; i++) { 
            data_List.add( Integer.parseInt(datas[i])); 
        } 
    } 
     
    public int[][] getData() { 
        for(int i=0; i<20; i++) { 
            for(int j=0; j<20; j++) { 
                data[i][j] = data_List.get( i*20 + j); 
            } 
        } 
         
        return data; 
    } 

    public ArrayList<Integer> getDataList() { 
        return data_List; 
    } 

    public long calRow(int x, int y) {
        long result = 1; 
         
        for(int i=0; i<4; i++) { 
            result *= data[y][x+i]; 
        } 
         
        return result; 
    } 

    public long calCol(int x, int y) {
        long result = 1; 
         
        for(int i=0; i<4; i++) { 
            result *= data[y+i][x]; 
        } 
         
        return result; 
    } 

    public long calRowCol_Up(int x, int y) {
        long result = 1; 
         
        for(int i=0; i<4; i++) { 
            result *= data[y-i][x+i]; 
        } 
         
        return result; 
    } 

    public long calRowCol_Down(int x, int y) {
        long result = 1; 
         
        for(int i=0; i<4; i++) { 
            result *= data[y+i][x+i]; 
        } 
         
        return result; 
    } 

}