2D Arrays

문제

6x6 2차원 배열이 주어졌을 경우, hourglasses 를 이루는 영역의 합의 최대값을 구하는 문제이다.

 

해법. 3x3 마스킹 역할을 하는 포문을 만들고, 그것을 x축으로 3번, y축으로 3번 반복한다.

-- PSEUDO CODE
INIT
	int x = 0;
	int y = 0;

WHILE y < 4	
	WHILE x < 4	
		FOR i=0. i<4 -- 3번반복 (6x6 배열이고, 마스킹의 사이즈는 3이기 때문에)
			FOR j=0, j<4
				IF i == 1 THEN
					arr[i+y][1+x];
				ELSE
					arr[i+y][j+x];
		x ++;
	END WHILE
	x = 0;
	y ++;
	
END

 

TestCase 2개를 틀려서, 보니 max 값을 0으로 처음에 잡아놨었다. 그러면 arr에 있는 값이 모두 음수일 경우 0이 크기때문에, 결과값이 0으로 틀리게 나온다.  

이 문제에서는 배열 안에 있는 값이 [-9, 9] 사이라 그래서, max를 -45로 잡았다. 

더 좋은 방법은 Integer.MIN_VALUE 를 사용한다.

int x = 0;
int y = 0;

int max = Integer.MIN_VALUE;
while (y < 4) {
	while (x < 4) {
		
		int sum = 0;
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				
				if(i == 1) {
					sum += arr[i+y][1+x];
					break;
				} else {
					sum += arr[i+y][j+x];
				}
				
			}
		}

		if(sum > max) {
			max = sum;
		}
		
		x ++;
	}
	y++;
	x = 0;
}

System.out.print(max);

---

이 문제에서는 배열의 사이즈를 6x6으로 고정시켰지만, 무한히 큰 배열일 경우 아마 이 해답은 옳지 않을 수도 있다. 더 좋은 방법이 있을까?

 

 

체크포인트:

• hourglasses : 모래시계 ㅋㅋ

Github 주소:

https://github.com/mongsilJeong/algorithm/blob/master/src/algorithm/codingInterview/datastructure/arrayString/EditString.javaExcercise.java