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

🧩 문제

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

프로그래머스

 

💡 내가 작성한 코드

• 처음에 문제를 보고 든 생각은
  • n x n 배열을 만들고, 그 배열을 1차원 배열로 펼친 후, 특정 구간의 값을 반환하는 것이었습니다.
  • 즉, 문제에서 주어진 n을 활용하여 2차원 배열을 생성한 후, 1차원 배열로 변환하여 해결하려고 했습니다.
  • 하지만 2차원 배열을 모두 생성하는 것은 메모리 낭비라는 것을 깨닫고 더 효율적인 방법을 생각했습니다.

 

🪄 문제 해결 과정

1. 2차원 배열(3 x 3)을 1차원 배열로 변경하였을 때 인덱스 값 생각해보기

	0	1	2
0	1 (0, 0)	2 (0, 1)	3 (0, 2)
1	2 (1, 0)	2 (1, 1)	3 (1, 2)
2	3 (2, 0)	3 (2, 1)	3 (2, 2)

• 위의 2차원 배열을 행을 기준으로 1차원 배열로 변경한다면
  • `[ (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2) ]` -> `(row, col)` 형태로 변경됩니다
  • 3 x 3 배열을 기준으로 앞에서부터 3개씩 나눠서 보면, row는 고정값이고 col은 증가하는 것을 확인할 수 있습니다.
• 따라서 1차원 배열의 인덱스를 2차원 배열의 인덱스로 변환하는 공식은 아래와 같게 됩니다.
  • `row = i / n`
  • `col = i % n`

  2. 효율적인 접근을 위해 전체 배열을 생성하지 않고 필요한 구간(`left ~ right`)의 값만 계산

 

class Solution {
    public int[] solution(int n, long left, long right) {
        int length = (int)(right - left + 1);
        int[] answer = new int[length];
        for (long i = left; i <= right; i++) {
            int row = (int)(i / n) + 1;
            int col = (int)(i % n) + 1;
            answer[(int)(i - left)] = Math.max(row, col);
        }
        return answer;
    }
}

1. left ~ right 사이의 값들만 배열로 반환하기 위해 길이가 `right - left - 1`인 answer 배열 선언
2. left ~ right 까지의 인덱스를 반복문으로 순회
   • 인덱스 `i`를 2차원 배열의 `(row, col)` 위치로 변환한 다음, `Math.max(row, col) + 1`를 사용하여 해당 위치에 들어갈 값을 계산
   • `Math.max(row, col) + 1`를 사용해서 둘 중의 큰 값 + 1 을 하는 이유는, 위의 표를 보면 값이 항상 row와 col 중 더 큰 값에 +1을 하면 해당 위치의 값이 됨
     • ex) row = 1 이고 col = 2 인 위치의 값은 3