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

문제 링크

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

프로그래머스

 

 

문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어 붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

 

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

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

 

 

입출력 예

n	left	right	result
3	2	5	[3, 2, 2, 3]
4	7	14	[4, 3, 3, 3, 4, 4, 4, 4]

 

 

입출력 예 설명

입출력 예 #1

다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

 

입출력 예 #2

다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

 

 

코드

class Solution {
    public int[] solution(int n, long left, long right) {
        int len = (int) (right - left);  // 변환할 숫자의 개수
        int[] answer = new int[len + 1]; // 변환된 숫자를 저장할 배열
        int idx = 0; // answer 배열의 위치 인덱스

        // left부터 right까지의 숫자들에 대해 반복
        for (long i = left; i <= right; i++) {
            long row = i / n; // 현재 숫자의 행 번호
            long col = i % n; // 현재 숫자의 열 번호

            // 행과 열 중 더 큰 값에 1 더하여 저장
            answer[idx++] = Math.max((int) row, (int) col) + 1;
        }

        return answer;
    }
}

코드 설명

주석 참고

• 이 문제는 주어진 범위 내의 숫자들을 활용하여 2차원 배열 상의 숫자들을 1차원 배열로 변환하여 반환하는 문제다.
• 입력 값 left와 right는 범위가 매우 클 수 있으므로 2차원 배열을 생성하여 값을 추론하기엔 시간이 부족하다.
• 따라서 문제의 규칙을 찾아 수학적 계산을 통해 1차원 배열을 완성해야 한다.
• 다음은 n이 4일 때 2차원 배열을 표현한 표다.

	0	1	2	3
0	1	2	3	4
1	2	2	3	4
2	3	3	3	4
3	4	4	4	4

• 위 표를 살펴보면 행 [0, 0]은 1, [0, 1], [1, 0], [1, 1]은 2이며 행과 열이 증가함에 따라 값도 증가하고 있다.
• 표를 통해 행과 열의 번호 중 큰 값에 1을 더한 값이 해당 위치의 값이 되는 것을 알 수 있다.
• 따라서 각 행과 열의 위치 값을 비교하여 큰 번호에 1을 더하여 answer 배열에 저장하면 된다.
• 현재 위치 값을 n으로 나눈 값은 행, n으로 나눈 나머지 값은 열 번호가 된다.
• left부터 right까지 반복하여 반복자 i를 통해 행과 열 번호를 구한 뒤 큰 값에 1을 더하여 answer 배열에 0부터 담으면 된다.