Hackerrank Day 11 2D Arrays

알고리즘 연습 사이트
www.hackerrank.com


Day 11:2D Arrays


이번 문제는 아래 예시의 6x6 배열이 주어지는데,

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

위 배열에서 3x3의 모래시계 모양을 만들 수 있는 가짓수는 16가지가 된다.

1 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 2 0 2 4 2 4 4 4 4 0 1 1 1 1 1 0 1 0 0 0 0 0 0 2 4 4 0 0 0 0 0 2 0 2 0 2 0 0 0 0 2 0 2 4 2 4 4 4 4 0 0 0 2 0 0 0 1 0 1 2 1 2 4 2 4 0

이 모래시계들의 합 중 가장 큰 값을 찾는 것이 Day 11의 문제이다.

아래 코드를 작성하다 보니 for문 중첩이 4개나 되어버렸다.
우선 가장 바깥 for문 2개는 전체 모래시계의 반복 16가지를 뜻한다.
그리고 안쪽의 for문 2개는 모래시계를 구성하는 요소 9가지를 뜻한다.

if문 안의 조건의 의미는 모래시계 요소가 아닌 것들의 인자들만 빼고 모조리 다 더하겠다는 의미이다.
arr[k+i][z+j] 라고 작성한 이유는 행과 열을 더해줘야 모래시계가 옆으로 한칸씩 이동하거나 아래로 내려가면서 위치가 이동되기 때문이다.

int[] sum = new int[16];
int number = 0;
int max = 0;
for(int i=0 ; i<4 ; i++){ // 행   
    for(int j=0 ; j < 4 ; j++ ){ //열
        for(int k=0; k<3 ; k++ ){
            for(int z=0 ; z<3 ; z++ ){
                if( !(k==1&&z==0) && !(k==1&&z==2))
                    sum[number] += arr[k+i][z+j];
            }  
        }
        if(sum[number] > max || (i ==0 && j ==0)){
            max = sum[number];
        }
        number++;
    }
}
System.out.println(max);

max값을 구하는 것은 이전 Day 10 문제에서 삽질을 좀 해서(?) 이번엔 쉽게 이해하였다.
max값을 대입하는 과정에서 (i ==0 && j ==0) 조건이 추가가 된 이유는, 이 조건을 안 넣으면 max값이 음수인 경우에 문제가 된다.

첫 모래시계의 sum 값을 반드시 max 에 대입하여 최대값이 음수일 때에도 정확하게 출력되게 해야한다.

cf ) 아래와 같이 sort를 사용해서도 max값을 출력할 수 있다.

Arrays.sort(sum); //기본 오름차순 정렬
System.out.println(sum[sum.lenght-1]);