알고리즘) N*N 격자판의 최대합

 자연수 N이 주어지면 N*N 만큼 숫자가 주어진다. 이 격자판에서의 각 행, 열, 대각선의 합 중 가장 큰 값을 구하는 문제이다.

초기 작성 코드

import java.util.Scanner;

public class Main {
    private int solution (int num, int[][] grid) {
        int answer = 0;

        // 행의 합 중 가장 큰 값 도출
        for (int i = 0; i < num; i++) {
            int sum = 0;
            for (int j = 0; j < num; j++) {
                sum += grid[i][j];
            }
            if (sum > answer) answer = sum;
        }

        // 열의 합 중 가장 큰 값 도출
        for (int i = 0; i < num; i++) {
            int sum = 0;
            for (int j = 0; j < num; j++) {
                sum += grid[j][i];
            }
            if (sum > answer) answer = sum;
        }

        // 대각선의 합 중 가장 큰 값 도출
        int diagonal = 0;
        for (int i = 0; i < num; i++) diagonal += grid[i][i];
        if (diagonal > answer) answer = diagonal;

        // 역대각선의 합 중 가장 큰 값 도출
        int revDiagonal = 0;
        for (int i = num - 1; i >= 0; i--) revDiagonal += grid[i][i];
        if (revDiagonal > answer) answer = revDiagonal;
        
        return answer;
    }

    public static void main(String[] args) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.nextLine();

        int[][] grid = new int[num][num];
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        System.out.println(al.solution(num, grid));
    }
}

 

개선된 코드

import java.util.Scanner;

public class Main {
    private int solution (int num, int[][] grid) {
        int answer = 0;

        int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                sum1 += grid[i][j];
                sum2 += grid[j][i]; // i, j를 서로 바꾸면 열의 합을 구할 수 있음
            }
            answer = Math.max(answer, sum1);
            answer = Math.max(answer, sum2);
            sum1 = sum2 = 0;
        }


        for (int i = 0; i < num; i++) {
            sum3 += grid[i][i];
            sum4 += grid[i][num - i - 1];
        }

        answer = Math.max(answer, sum3);
        answer = Math.max(answer, sum4);

        return answer;
    }

    public static void main(String[] args) {
        Main al = new Main();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.nextLine();

        int[][] grid = new int[num][num];
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                grid[i][j] = sc.nextInt();
            }
        }
        System.out.println(al.solution(num, grid));
    }
}

 

 쉬운 내용이지만 나는 총 네 번의 for문을 돌렸고, 심지어 두 개는 이중 for문이었다. 조금이라도 더 효율적인 코드를 짜기 위해서는 알고리즘 공부가 필수임을 느낀다.