n^2 배열 자르기

n*n배열을 주어진 left, right 인덱스 범위로 1차원 배열만들기

 

ex: n = 3, left = 2, right = 5

123

223

333

-> 3,2,2,3

 

처음에는 단순히 배열을 만들어서 인덱스를 자르려고 함

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

하지만 제한사항으로 인하여 불가능....

• 1 ≤ n ≤ 10^7
• 0 ≤ left ≤ right < n^2
• right - left < 10^5

해결방안

1. 2차원 배열의 값은 좌표 x,y의 max값 + 1로 구성된다.

값 (x, y)
1 (0,0)	2 (0,1)	3 (0,2)
2 (1,0)	2 (1,1)	3 (1,2)

2. 인덱스(left ~ right)의 좌표 x,y를 알 수 있음

//행

x = index / n 

//열

y = index % n

 

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

        int cnt = 0;
        for(long i=left; i<=right; i++){
            long r = i/n; //index가 가리키는 x좌표
            long c = i%n; //index가 가리키는 y좌표
            // list.add(Math.max(r,c)+1);
            answer[cnt]=(int)(Math.max(r,c)+1);
            cnt++;
            
        }

        return answer;
    }

 

 

수학적으로 생각해야되는 문제들을 많이 풀어봐야겠다.

 

 

 

 

코딩테스트 연습 월간 코드 챌린지 시즌3 n^2 배열 자르기

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