[프로그래머스] Lv.2: n^2 배열 자르기 - java

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

접근법

문제를 처음에 봤을 때는 문제에서 요구하는 그대로 2차원 배열을 만들어서 하면 되겠다고 생각했지만, n의 범위가 최대 $10^7$ 이므로 2차원 배열을 생성하기엔 힘드니 규칙을 찾아야겠다고 생각했다. 규칙을 찾기 위해 문제를 그려보며 생각했다.

 

예제

입출력 예의 두번째를 한번 그려보자. 

n = 4, left = 7, right = 14

이 2차원 배열을 각 행씩 잘라서 붙이면 아래와 같고, 색칠한 부분을 구하면 된다.

다시 2차원 배열에 left ~ right 배열을 색칠해보자.

즉 우리는 arr[1][3] ~ arr[3][3]를 구해야 되는 것이다. 여기서 우리는 규칙을 찾을 수 있다.

left / n = 시작점의 행
left % n = 시작점의 열
right / n = 마지막점의 행
right % n = 마지막점의 열

 

이제 각 위치에서 갖는 값의 규칙을 찾으면 된다.

i번째 행에서 i번째 열까지는 전부 i 인 것을 쉽게 알 수 있다. (i + 1)열까지는 하나씩 증가해주면 된다. 간단하게 정리해보자.

[i][0] ~ [i][i] = i
[i][j] = i + (j - i), i < j

 

이제 코드를 작성하기만 하면 된다. 코드로 바꾸는 과정이 약간 어려웠던 것 같다. 아래 내 코드를 보지 말고 먼저 작성해보는 것을 추천한다!

 

코드

class Solution {
    public int[] solution(int n, long left, long right) {
        // 시작, 끝 행과 열 계산
        int startR = (int) (left / n);
        int startC = (int) (left % n);
        int endR = (int) (right / n);
        int endC = (int) (right % n);
        
        int length = (endR - startR + 1) * n - (startC + n - endC - 1); // 자른 배열의 길이
        int[] answer = new int[length];
        int idx = 0;
        
        while (idx < length) {
            int c = startC % n;
            
            if (c <= startR) {
                answer[idx++] = startR + 1;
            } else {
                answer[idx++] = startR + (c - startR) + 1;
            }
            
            if (++startC % n == 0) {
                startR++;
            }
        }
        
        return answer;
    }
}