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

문제

이 문제는 애니메이션을 보는 것이 이해가 빠르기 때문에 문제 원본을 첨부한다.

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

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

 

풀이코드

public int[] solution(int n, long left, long right) {   //n^2배열 자르기
    int[] answer = new int[(int)(right-left)+1];        //left index부터 right index까지 저장할 배열 생성
    int cnt = 0;                                        //answer의 index값을 조절할 변수 생성
    while(left<=right) {
        answer[cnt++] = (int)Math.max(left/n, left%n)+1;//answer배열에 값을 차례대로 집어넣는다.
        left++;
    }
    return answer;
}

솔직히 처음에는 n*n배열을 다 만들어서 풀려고 했는데...문제에서 n의 범위가 10^7까지인데 n*n을 하면 가볍게 int의 범위를 넘겨서 배열을 다 만들어서 풀면 안되었다...그래서 처음부터 차근차근 생각해봤는데 일단 배열을 규칙부터 찾아봤다.

n = 4일때, (행,열) 순으로 배열을 완성하면

              (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) 순으로 배열되고

index 번호  0     1     2     3     4     5     6     7     8     9    10   11   12    13   14    15  이렇게 되는데

여기서 규칙을 찾아보니 (a,b)로 나타낸다고 쳤을 때, index번호 = n*a + b가 되었다!

그래서 이것을 활용하면 index번호/n = a가 되고 index번호%n = b가 된다.

 

그리고

(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3) 여기에서 들어가는 번호를 계산하면

  1     2     3     4    2     2     3     4     3     3     3     4     4     4     4     4   이렇게 번호가 들어간다.

여기서도 규칙이 하나 나오는데 (a,b)로 나타낸다고 쳤을 때, (a와 b중에 큰 수+1)이 번호로 들어간다.

이것들을 활용하면

answer[cnt++] = (int)Math.max(left/n, left%n)+1;

이 코드가 나오는 것이고 나머지는 주석에 설명을 달아놓아서 쉽게 이해할 수 있을 것이다.