n^2 배열 자르기

문제

정수 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차원 배열을 left 인덱스부터 right 인덱스까지 잘라낸 배열을 반환하는 문제입니다.

• 입력: 정수 n (1 ≤ n ≤ 10^7), left, right (0 ≤ left ≤ right < n^2, right - left < 10^5)
• 출력: 조건에 맞게 잘라낸 1차원 정수 배열

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

풀이: 좌표 변환 공식과 규칙성을 활용한 수학적 탐색

이 문제에서 n은 최대 10^7입니다. 만약 문제의 설명대로 N * N 크기의 2차원 배열을 실제로 생성한다면 최대 10^14개의 원소가 필요하므로 무조건 메모리 초과(Memory Limit Exceeded)가 발생합니다. 따라서 배열을 만들지 않고 인덱스 간의 수학적 규칙을 찾아야 합니다.

• 1차원 인덱스를 2차원 좌표로 변환: 1차원 배열에서의 인덱스 i가 주어졌을 때, 이를 N * N 2차원 배열의 좌표 (y, x)로 변환하는 공식은 다음과 같습니다.
  • 행(Row) 좌표 y = i / n
  • 열(Column) 좌표 x = i % n
• 좌표의 값 계산 규칙: 문제의 규칙에 따라 칸을 채워보면, 특정 좌표 (y, x)에 들어가는 숫자는 행과 열 인덱스 중 더 큰 값에 1을 더한 값과 같다는 것을 알 수 있습니다.
  • 값 = Math.max(y, x) + 1
• 구간 반복 및 자료형 주의: 실제 필요한 구간인 left부터 right까지만 반복문을 순회합니다. 여기서 left와 right는 최대 10^14에 달할 수 있으므로, 반복문 제어 변수 i와 좌표 계산 변수 y, x는 반드시 long 타입을 사용해야 정수 오버플로우를 방지할 수 있습니다. 계산된 결과값은 문제의 요구사항에 맞게 int형으로 캐스팅하여 배열에 담습니다.

코드

class Solution {
    public int[] solution(int n, long left, long right) {
        // 결과 배열의 크기는 (right - left + 1)
        int[] ans = new int[(int)(right - left + 1)];

        // 필요한 구간(left ~ right)만 순회
        for (long i = left; i <= right; i++) {
            // 1차원 인덱스를 2차원 좌표(y, x)로 변환
            long y = i / n;
            long x = i % n;
            
            // 해당 좌표의 값은 행과 열 중 최댓값 + 1
            ans[(int)(i - left)] = (int)(Math.max(y, x) + 1);
        }
        
        return ans;
    }
}

알고리즘 분류

수학 (Mathematics), 구현 (Implementation)