프로그래머스 | Level 2 | n^2 배열 자르기

Programmers | Level 2 | n^2 배열 자르기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Simulation

Description

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

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

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

Constraints

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

Examples

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

Solutions

• ⏳ Time Complexity: O(n)
• 💾 Space Complexity: O(n)

import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        // 결과 배열 길이 계산 및 초기화
        int length = (int) (right - left) + 1;
        int[] result = new int[length];
        
        int index = 0;
        // left부터 right까지 순회
        for (long i = left; i <= right; i++) {
            // 행과 열 계산
            int row = (int) (i / n);
            int col = (int) (i % n);
            // 각 요소 값 계산 및 저장
            result[index++] = Math.max(row, col) + 1;
        }
        
        // 결과 배열 반환
        return result;
    }
}

Approaches

이 문제는 2차원 배열을 직접 생성하지 않고, 주어진 left와 right 인덱스 범위에 해당하는 1차원 배열 부분만을 계산하여 효율적으로 처리하는 문제입니다. 이를 위해 다음과 같은 과정을 거칩니다:

• 1차원 배열 인덱스로 접근:
  • 2차원 배열을 직접 생성하지 않고, left와 right 범위 내의 1차원 배열 부분만을 계산합니다.
  • 2차원 배열의 각 요소 (i, j)는 1차원 배열에서 i * n + j로 접근할 수 있습니다. 여기서 i는 행 인덱스, j는 열 인덱스를 나타냅니다. 예를 들어, n이 3일 때, 2차원 배열의 (2, 1) 요소는 1차원 배열의 2 * 3 + 1 = 7번째 요소에 해당합니다.
  • 각 요소의 값은 Math.max(i / n, i % n) + 1로 계산할 수 있습니다. 이는 각 2차원 배열의 값이 해당 행과 열의 인덱스 중 큰 값에 1을 더한 값이기 때문입니다. 예를 들어, (2, 1) 요소의 값은 Math.max(2, 1) + 1 = 3이 됩니다. 이는 문제 설명에서 2차원 배열을 채우는 방식과 일치합니다.
• 부분 배열 계산:
  • left부터 right까지의 인덱스를 순회하면서 각 요소의 값을 계산하여 결과 배열에 저장합니다.
  • 이러한 접근 방식은 2차원 배열을 생성하는데 필요한 메모리와 연산 시간을 절약하며, 필요한 부분만을 계산하기 때문에 효율적입니다.

이 알고리즘은 전체 2차원 배열을 생성하는 대신 필요한 부분만 계산하여 메모리 사용을 최소화하고, 연산 시간을 절약하여 문제를 효율적으로 해결할 수 있도록 설계되었습니다. 시간 복잡도는 O(n), 공간 복잡도는 O(n)으로, 주어진 문제를 효율적으로 해결하는 데 충분합니다.