JAVA 알고리즘 : 6 x 6 배열 안의 모래시계집합들의 합 중 최대합 구하기

스터디사이트 : https://www.hackerrank.com

JAVA 알고리즘 : 6 x 6 배열 안의 모래시계집합들의 합 중 최대합 구하기

※ 코딩실습 - 조건

6 x 6 배열을 3x3크기의 모래시계모양의 집합 16개로 각자 쪼개서 만든 후,

그 16개의 집합들 각자의 합 중 제일 합이 큰 모래시계집합의 합을 구하면 된다. (말이 좀 어렵다..ㅋ)

제약조건이라 함은 단지 각 배열에 들어가야 할 수의 범위는 -9부터 9까지라는 것뿐이다.

모래시계집합 변환과정은 직접 그림으로 확인 해 보시라.

변환과정

   

 결과

    

입력

1 1 1 0 0 0

0 1 0 0 0 0

1 1 1 0 0 0

0 0 2 4 4 0

0 0 0 2 0 0

0 0 1 2 4 0

출력

19        ←   2 4 4
  2
1 2 4  배열의 합이 모래시계집합들의 합 중 최대.

디버깅

일단 여기서 코딩으로 힌트를 줬다.

public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int arr[][] = new int[6][6];

        for(int i=0; i < 6; i++){

            for(int j=0; j < 6; j++){

                arr[i][j] = in.nextInt();

            }

        }

}

i 는 행이고, j 는 열이도다..

문제를 준 사이트에서 Scanner를 통하여 입력을 다 할 것이고.. 여기까지가 다이다..;

아래처럼 엑셀에서도 써가며.. 몇번을 지우고 쓰며 디버깅을 해 보았다.

모래시계집합의 행열주소모래시계집합의 번호를 hourglass로 매겨서 Key값으로 넣었다.

코딩으로 변환한 모습. list는 HashMap클래스이고, key값은 hourglass이다.

public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); int arr[][] = new int[6][6]; int hourglass=0; int sum = 0; int sum_center=0; int maxsum=-99; // maxsum : 음수일때 대비를 안했다. Map<Integer, Integer> sums = new HashMap<Integer, Integer>(); // 입력값 배열에 집어넣기 for(int i=0; i < 6; i++){ for(int j=0; j < 6; j++){ arr[i][j] = in.nextInt(); } //end for } //end for for(int j=0; j<4; j++){ //>> 행증가 for(int k=0; k<4; k++){ //>> 열증가 hourglass++; for(int cnt=0; cnt<3; cnt++){ //>> 집합 내 행증가 for(int i=k; i<k+3; i++){ //>> 집합 내 열증가 if(cnt==0){ sum = sum + arr[j][i]; }else if(cnt==1){ sum_center=arr[j+1][k+cnt]; System.out.printf("arr[%d][%d] / ", j+1, k+cnt); }else if(cnt==2){ sum = sum + arr[j+2][i]; } //end if System.out.printf("cnt)%d, i)%d : sum : %d, sum_center : %d\n", cnt, i, sum, sum_center); } //end for i } //end for cnt sums.put(hourglass, sum+sum_center); sum=0; sum_center=0; System.out.printf("hourglass(%d) : %d\n", hourglass, sums.get(hourglass)); System.out.printf("sums.get(%d) = %d, maxsum = %d\n", hourglass, sums.get(hourglass), maxsum); if(sums.get(hourglass) > maxsum){ // maxsum : 음수일때 대비를 안했다. maxsum = sums.get(hourglass); System.out.println("maxsum is changed : " + maxsum); } System.out.printf("maxsum is now : %d\n----------------------------\n", maxsum); } //end for k } //end for j System.out.println("maxsum is now : "+ maxsum); System.out.printf("\nsums.size : %d", sums.size()); } // end main

결과 :  cnt)0, i)0 : sum : 1, sum_center : 0 cnt)0, i)1 : sum : 2, sum_center : 0 cnt)0, i)2 : sum : 3, sum_center : 0 arr[1][1] / cnt)1, i)0 : sum : 3, sum_center : 1 arr[1][1] / cnt)1, i)1 : sum : 3, sum_center : 1 arr[1][1] / cnt)1, i)2 : sum : 3, sum_center : 1 cnt)2, i)0 : sum : 4, sum_center : 1 cnt)2, i)1 : sum : 5, sum_center : 1 cnt)2, i)2 : sum : 6, sum_center : 1 hourglass(1) : 7 sums.get(1) = 7, maxsum = -99 maxsum is changed : 7 maxsum is now : 7 ---------------------------- cnt)0, i)1 : sum : 1, sum_center : 0 cnt)0, i)2 : sum : 2, sum_center : 0 cnt)0, i)3 : sum : 2, sum_center : 0 arr[1][2] / cnt)1, i)1 : sum : 2, sum_center : 0 arr[1][2] / cnt)1, i)2 : sum : 2, sum_center : 0 arr[1][2] / cnt)1, i)3 : sum : 2, sum_center : 0 cnt)2, i)1 : sum : 3, sum_center : 0 cnt)2, i)2 : sum : 4, sum_center : 0 cnt)2, i)3 : sum : 4, sum_center : 0 hourglass(2) : 4 sums.get(2) = 4, maxsum = 7 maxsum is now : 7 ---------------------------- cnt)0, i)2 : sum : 1, sum_center : 0 cnt)0, i)3 : sum : 1, sum_center : 0 cnt)0, i)4 : sum : 1, sum_center : 0 arr[1][3] / cnt)1, i)2 : sum : 1, sum_center : 0 arr[1][3] / cnt)1, i)3 : sum : 1, sum_center : 0 arr[1][3] / cnt)1, i)4 : sum : 1, sum_center : 0 cnt)2, i)2 : sum : 2, sum_center : 0 cnt)2, i)3 : sum : 2, sum_center : 0 cnt)2, i)4 : sum : 2, sum_center : 0 hourglass(3) : 2 sums.get(3) = 2, maxsum = 7 maxsum is now : 7 ---------------------------- cnt)0, i)3 : sum : 0, sum_center : 0 cnt)0, i)4 : sum : 0, sum_center : 0 cnt)0, i)5 : sum : 0, sum_center : 0 arr[1][4] / cnt)1, i)3 : sum : 0, sum_center : 0 arr[1][4] / cnt)1, i)4 : sum : 0, sum_center : 0 arr[1][4] / cnt)1, i)5 : sum : 0, sum_center : 0 cnt)2, i)3 : sum : 0, sum_center : 0 cnt)2, i)4 : sum : 0, sum_center : 0 cnt)2, i)5 : sum : 0, sum_center : 0 hourglass(4) : 0 sums.get(4) = 0, maxsum = 7 maxsum is now : 7 ---------------------------- cnt)0, i)0 : sum : 0, sum_center : 0 cnt)0, i)1 : sum : 1, sum_center : 0 cnt)0, i)2 : sum : 1, sum_center : 0 arr[2][1] / cnt)1, i)0 : sum : 1, sum_center : 1 arr[2][1] / cnt)1, i)1 : sum : 1, sum_center : 1 arr[2][1] / cnt)1, i)2 : sum : 1, sum_center : 1 cnt)2, i)0 : sum : 1, sum_center : 1 cnt)2, i)1 : sum : 1, sum_center : 1 cnt)2, i)2 : sum : 3, sum_center : 1 hourglass(5) : 4 sums.get(5) = 4, maxsum = 7 maxsum is now : 7 ---------------------------- cnt)0, i)1 : sum : 1, sum_center : 0 cnt)0, i)2 : sum : 1, sum_center : 0 cnt)0, i)3 : sum : 1, sum_center : 0 arr[2][2] / cnt)1, i)1 : sum : 1, sum_center : 1 arr[2][2] / cnt)1, i)2 : sum : 1, sum_center : 1 arr[2][2] / cnt)1, i)3 : sum : 1, sum_center : 1 cnt)2, i)1 : sum : 1, sum_center : 1 cnt)2, i)2 : sum : 3, sum_center : 1 cnt)2, i)3 : sum : 7, sum_center : 1 hourglass(6) : 8 sums.get(6) = 8, maxsum = 7 maxsum is changed : 8 maxsum is now : 8 ---------------------------- cnt)0, i)2 : sum : 0, sum_center : 0 cnt)0, i)3 : sum : 0, sum_center : 0 cnt)0, i)4 : sum : 0, sum_center : 0 arr[2][3] / cnt)1, i)2 : sum : 0, sum_center : 0 arr[2][3] / cnt)1, i)3 : sum : 0, sum_center : 0 arr[2][3] / cnt)1, i)4 : sum : 0, sum_center : 0 cnt)2, i)2 : sum : 2, sum_center : 0 cnt)2, i)3 : sum : 6, sum_center : 0 cnt)2, i)4 : sum : 10, sum_center : 0 hourglass(7) : 10 sums.get(7) = 10, maxsum = 8 maxsum is changed : 10 maxsum is now : 10 ---------------------------- cnt)0, i)3 : sum : 0, sum_center : 0 cnt)0, i)4 : sum : 0, sum_center : 0 cnt)0, i)5 : sum : 0, sum_center : 0 arr[2][4] / cnt)1, i)3 : sum : 0, sum_center : 0 arr[2][4] / cnt)1, i)4 : sum : 0, sum_center : 0 arr[2][4] / cnt)1, i)5 : sum : 0, sum_center : 0 cnt)2, i)3 : sum : 4, sum_center : 0 cnt)2, i)4 : sum : 8, sum_center : 0 cnt)2, i)5 : sum : 8, sum_center : 0 hourglass(8) : 8 sums.get(8) = 8, maxsum = 10 maxsum is now : 10 ---------------------------- cnt)0, i)0 : sum : 1, sum_center : 0 cnt)0, i)1 : sum : 2, sum_center : 0 cnt)0, i)2 : sum : 3, sum_center : 0 arr[3][1] / cnt)1, i)0 : sum : 3, sum_center : 0 arr[3][1] / cnt)1, i)1 : sum : 3, sum_center : 0 arr[3][1] / cnt)1, i)2 : sum : 3, sum_center : 0 cnt)2, i)0 : sum : 3, sum_center : 0 cnt)2, i)1 : sum : 3, sum_center : 0 cnt)2, i)2 : sum : 3, sum_center : 0 hourglass(9) : 3 sums.get(9) = 3, maxsum = 10 maxsum is now : 10 ---------------------------- cnt)0, i)1 : sum : 1, sum_center : 0 cnt)0, i)2 : sum : 2, sum_center : 0 cnt)0, i)3 : sum : 2, sum_center : 0 arr[3][2] / cnt)1, i)1 : sum : 2, sum_center : 2 arr[3][2] / cnt)1, i)2 : sum : 2, sum_center : 2 arr[3][2] / cnt)1, i)3 : sum : 2, sum_center : 2 cnt)2, i)1 : sum : 2, sum_center : 2 cnt)2, i)2 : sum : 2, sum_center : 2 cnt)2, i)3 : sum : 4, sum_center : 2 hourglass(10) : 6 sums.get(10) = 6, maxsum = 10 maxsum is now : 10 ---------------------------- cnt)0, i)2 : sum : 1, sum_center : 0 cnt)0, i)3 : sum : 1, sum_center : 0 cnt)0, i)4 : sum : 1, sum_center : 0 arr[3][3] / cnt)1, i)2 : sum : 1, sum_center : 4 arr[3][3] / cnt)1, i)3 : sum : 1, sum_center : 4 arr[3][3] / cnt)1, i)4 : sum : 1, sum_center : 4 cnt)2, i)2 : sum : 1, sum_center : 4 cnt)2, i)3 : sum : 3, sum_center : 4 cnt)2, i)4 : sum : 3, sum_center : 4 hourglass(11) : 7 sums.get(11) = 7, maxsum = 10 maxsum is now : 10 ---------------------------- cnt)0, i)3 : sum : 0, sum_center : 0 cnt)0, i)4 : sum : 0, sum_center : 0 cnt)0, i)5 : sum : 0, sum_center : 0 arr[3][4] / cnt)1, i)3 : sum : 0, sum_center : 4 arr[3][4] / cnt)1, i)4 : sum : 0, sum_center : 4 arr[3][4] / cnt)1, i)5 : sum : 0, sum_center : 4 cnt)2, i)3 : sum : 2, sum_center : 4 cnt)2, i)4 : sum : 2, sum_center : 4 cnt)2, i)5 : sum : 2, sum_center : 4 hourglass(12) : 6 sums.get(12) = 6, maxsum = 10 maxsum is now : 10 ---------------------------- cnt)0, i)0 : sum : 0, sum_center : 0 cnt)0, i)1 : sum : 0, sum_center : 0 cnt)0, i)2 : sum : 2, sum_center : 0 arr[4][1] / cnt)1, i)0 : sum : 2, sum_center : 0 arr[4][1] / cnt)1, i)1 : sum : 2, sum_center : 0 arr[4][1] / cnt)1, i)2 : sum : 2, sum_center : 0 cnt)2, i)0 : sum : 2, sum_center : 0 cnt)2, i)1 : sum : 2, sum_center : 0 cnt)2, i)2 : sum : 3, sum_center : 0 hourglass(13) : 3 sums.get(13) = 3, maxsum = 10 maxsum is now : 10 ---------------------------- cnt)0, i)1 : sum : 0, sum_center : 0 cnt)0, i)2 : sum : 2, sum_center : 0 cnt)0, i)3 : sum : 6, sum_center : 0 arr[4][2] / cnt)1, i)1 : sum : 6, sum_center : 0 arr[4][2] / cnt)1, i)2 : sum : 6, sum_center : 0 arr[4][2] / cnt)1, i)3 : sum : 6, sum_center : 0 cnt)2, i)1 : sum : 6, sum_center : 0 cnt)2, i)2 : sum : 7, sum_center : 0 cnt)2, i)3 : sum : 9, sum_center : 0 hourglass(14) : 9 sums.get(14) = 9, maxsum = 10 maxsum is now : 10 ---------------------------- cnt)0, i)2 : sum : 2, sum_center : 0 cnt)0, i)3 : sum : 6, sum_center : 0 cnt)0, i)4 : sum : 10, sum_center : 0 arr[4][3] / cnt)1, i)2 : sum : 10, sum_center : 2 arr[4][3] / cnt)1, i)3 : sum : 10, sum_center : 2 arr[4][3] / cnt)1, i)4 : sum : 10, sum_center : 2 cnt)2, i)2 : sum : 11, sum_center : 2 cnt)2, i)3 : sum : 13, sum_center : 2 cnt)2, i)4 : sum : 17, sum_center : 2 hourglass(15) : 19 sums.get(15) = 19, maxsum = 10 maxsum is changed : 19 maxsum is now : 19 ---------------------------- cnt)0, i)3 : sum : 4, sum_center : 0 cnt)0, i)4 : sum : 8, sum_center : 0 cnt)0, i)5 : sum : 8, sum_center : 0 arr[4][4] / cnt)1, i)3 : sum : 8, sum_center : 0 arr[4][4] / cnt)1, i)4 : sum : 8, sum_center : 0 arr[4][4] / cnt)1, i)5 : sum : 8, sum_center : 0 cnt)2, i)3 : sum : 10, sum_center : 0 cnt)2, i)4 : sum : 14, sum_center : 0 cnt)2, i)5 : sum : 14, sum_center : 0 hourglass(16) : 14 sums.get(16) = 14, maxsum = 19 maxsum is now : 19 ---------------------------- maxsum is now : 19 sums.size : 16

코딩연습 & 결과

너무 생각할 게 많았다... 글로 다 옮겨적기 어려울거같다 ㅋ

나의 단점은 모든 과정을 다 모니터링을 하려 하다 보니 시간이 매우 오래 걸리는 것 같다는 것이다.

길게 보면 좋은 습관이지만, 결과만 출력하면 되는데 이런 디버깅을 넘 오래하는 것 같다 ㅋ 아래 사람이 작성한 간단한 코딩을 보면 더 허망하다 ㅋ

public static void main(String[] args) { Scanner in = new Scanner(System.in); int arr[][] = new int[6][6]; int hourglass=0; int sum = 0; int sum_center=0; int maxsum=-99; Map<Integer, Integer> sums = new HashMap<Integer, Integer>(); for(int i=0; i < 6; i++){ for(int j=0; j < 6; j++){ arr[i][j] = in.nextInt(); } } for(int j=0; j<4; j++){ //>> 행증가 for(int k=0; k<4; k++){ //>> 열증가 hourglass++; for(int cnt=0; cnt<3; cnt++){ //>> 집합 내 행증가 for(int i=k; i<k+3; i++){ //>> 집합 내 열증가 if(cnt==0){ sum = sum + arr[j][i]; }else if(cnt==1){ sum_center=arr[j+1][k+cnt]; }else if(cnt==2){ sum = sum + arr[j+2][i]; } //end if } //end for i } //end for cnt sums.put(hourglass, sum+sum_center); sum=0; sum_center=0; if(sums.get(hourglass) > maxsum){ maxsum = sums.get(hourglass); } } //end for k } //end for j System.out.println(maxsum); } //end main

결과 :  19

다른 사람의 초간단 코딩..

와 이사람은 하하.. ㅋ

입력부분을 제외하고

나는 for문 4번썼고 이 사람은 2번썼다.

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner in = new Scanner(System.in);
    int arr[][] = new int[6][6];
 
    // 입력값 배열에 집어넣기
    for(int i=0; i < 6; i++){
        for(int j=0; j < 6; j++){
            arr[i][j] = in.nextInt();
        } //end for
    } //end for
 
    int max = -64, temp;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            temp = arr[i][j] + arr[i][j+1] + arr[i][j+2] +
                arr[i+1][j+1] +
            arr[i+2][j] + arr[i+2][j+1] + arr[i+2][j+2];
            if (temp > max){
                max = temp;
            }
        }
    }
        System.out.println(max);
}