[Java] n^2 배열 자르기

프로그래머스

 

문제 풀이

제한 사항에 n이 10의 7승까지 주어진다. 문제에 주어진 그대로 풀이를 하면 (10^7) * (10^7)의 2차원 배열이 되기 때문에 메모리 초과, 시간 초과가 난다.

 

2차원 배열의 행들을 잘라 하나의 1차원 배열로 만들때 left ~ right 까지의 수를 구하는 문제이다.

1차원 배열로 만든다는 구문에서 일정한 규칙을 찾아 그에 해당하는 값들만 뽑아낼 수 있겠다는 생각을 했다.

 

처음 주목했던 것은 left 값에 따라서 처음 시작하는 값이 변한다는 것이었다. (어차피 left 부터 right값까지 구해야 하므로)

노리고 left 값을 주목했던 것은 아니었지만 left 값에 n을 나눈 몫을 2차원 배열의 row 값으로 활용할 수 있음을 깨달았다. 또한 나머지 값은 col 값으로 활용할 수도 있었다.

 

문제에서 주어진 2차원 배열에서의 값들을 1차원 배열로 나열하면 (1번 예시) 1,2,3,2,2,3,3,3,3 ... 이다. 그리고 인덱스 값과 함께 본다면 다음과 같다.

 

0 1 2 3 4 5 6 7 8
1 2 3 2 2 3 3 3 3 

 

아까 알아낸 row, col 값의 활용으로 답을 도출해보자. 2차원배열이라고 생각했을 때 다음과 같이 표기가 가능하다.

 

(1, 1) : 1,  (1, 2) : 2,  (1, 3) : 3,  (2, 1) : 2,  (2, 2) : 2 ,  (2, 3) : 3

 

즉 row, col의 max 값을 answer에 담아가는 것이 답이라는 것을 알 수 있다.

 

public int[] solution(int n, long left, long right) {
    int len = (int)(right - left) + 1;
    int[] answer = new int[len];

    for (int i = 0; i < len; i++) {
        int row = (int)(left / n + 1);
        int col = (int)(left % n + 1);
        left++;

        answer[i] = Math.max(row, col);
    }

    return answer;
}