[프로그래머스] n^2 배열 자르기 (Java)

📝 문제

코딩테스트 연습 - n^2 배열 자르기

 

🖥 풀이

import java.util.Arrays;

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int) (right - left + 1)];
		
		for (long i = left; i <= right; i++) {
			int row = (int) (i / n);
			int column = (int) (i % n);
			int idx = (int) (i - left);

			if (row < column)
				answer[idx] = column + 1;
			else
				answer[idx] = row + 1;
		}
		return answer;
    }
}

 

👩‍💻 시행 착오

문제를 처음 보고 우선 n x n 배열을 만들어줘야겠다는 생각을 해며 구현을 했다.

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        arr[i][j] = arr[j][i] = i + 1;

하지만, 이렇게 하면 메모리 초과가 뜬다......

그래서 n x n 배열을 만들어 주지 않고 구현을 해야 한다.

 

테스트 케이스를 예로 들어보자.

1 2 3
2 2 3
3 3 3

1 2 3 / 2 2 3 / 3 3 3

n x n 배열을 한 줄로 나열했을 때,

규칙을 보면 1행일 때 1열까지, 2행일 때 2열까지, 3행일 때 3열까지 같은 숫자가 나오는 것을 알 수 있다.

 

행보다 열이 같거나 작을 때 해당 값은 행의 값이고 행보다 열이 커질 때 해당 값은 열의 값이 된다.

 

이것을 이용해서 구현하면 메모리 초과를 벗어날 수 있다!