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

문제

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

프로그래머스

 

---

해설

n^2 배열 자르기 예시2 구현 (출처 - 프로그래머스)

문제의 예시 그림에서는 간단하게 붙이는 것으로 완성되지만 값의 범위들이 커 실제로 모두 구현하면 공간복잡도에 무리가 갈 수 있을 듯 합니다.

 

따라서 2차원 배열의 성질들을 통해 정답 배열에 어느 값이 들어가는지를 알면, right-left+1번만 계산을 하면 해결할 수 있을 것입니다.

 

각 칸의 요소는 좌표, 앞에서부터의 순서, 문제에서 들어가는 값 순으로 표시

문제의 목표는 left~right까지의 값들로 순서대로 이루어진 배열을 얻는 것입니다.

그렇다면 left번의 값을 구한다면 반복을 통해 해결 가능할 것 입니다.

예시로 가져온 그림에서 대표로 9번의 값을 가져와 보도록 하겠습니다.

 

특정 좌표 (i,j)에서의 순번을 구하려면 i * n + j로 구할 수 있습니다 -> (9 = 2 * 4 + 1)

따라서 역으로 순번을 통해 좌표의 값을 알아낼 수 있습니다 -> i = 순번 / n , j = 순번 % n

 

좌표를 통해 해당 값을 얻는 것은 i=j인 대각선을 기준으로 아래쪽은 i+1의 값, 위쪽은 j+1의 값을 가진 것을 알 수 있습니다.

이를 코드로 바꾸어 표현하여 해결하였습니다.

주의점

• 값의 범위가 커 long으로 되어있는 입력값에 염두하여 형변환을 한다.

---

코드

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] answer = new int[(int)(right-left)+1];
        int idx=0;
        
        // 각 순번별로 연산 진행
        for(long i=left;i<=right;i++){
        
        	// 해당 순번의 좌표 확인
            long x = i/n, y=i%n;
            
            // 좌표의 값이 어떤지 연산
            if(x<y) answer[idx]=(int)y+1;
            else answer[idx]=(int)x+1;
            idx++;
        }
        return answer;
    }
}