n^2 배열 자르기_복습

2026.07.19

문제 풀이

1차 실행 오류

---

45.0/100

런타임 오류, 메모리 초과

---

런타임 오류 원인 분석
left, right를 인덱스로 사용한 것이 원인임

Java에서는 int 타입만을 인덱스로 허용하는데, int로 표현할 수 없는 값을 변환하여 인덱스로 사용했기 때문에 값의 손실이 발생함

메모리 초과 원인 분석
int 배열은 $10^9$까지 범위를 표현 가능하지만,
문제 조건에서 n의 범위가 $10^7$이기 때문에 $10^{14}$까지의 범위를 표현할 수 있어야 함

따라서 n값에 대한 모든 수를 int 배열에 저장하는 것은 불가능함

new int[n * n]

해당 과정에서 또한 

n이 46,340 이하: 메모리는 부족하지만 오버플로는 없음 → 메모리 초과 발생
n이 46,341 이상: 오버플로 발생 → 런타임 오류 (NegativeArraySizeException 등)

---

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] arr = new int[n * n];
        int idx = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[idx++] = Math.max(i, j) + 1;
            }
        }
        int[] result = new int[(int)right - (int)left + 1];
        
        idx = 0;
        for (int i = (int)left; i <= (int)right; i++) {
            result[idx++] = arr[i];
        }
        
        return result;
    }
}

2차 실행 오류

---

55.0/100

실패

---

실패 원인 분석

int로 담을 수 없는 크기의 수를 변환 후 계산을 진행하여
int로 변환하는 과정에서 값이 손실됨

계산 후 변환 과정을 통해 int로 표현할 수 있는 수로 바꾼 후 변환함

---

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] result = new int[(int)right - (int)left + 1];

        int share = (int)left / n;
        int remain = (int)left % n;
        
        for (int i = 0; i < (int)right - (int)left + 1; i++) {
            result[i] = Math.max(share, remain) + 1;
            if (remain == n - 1) {
                share++;
                remain = 0;
            }
            else {
                remain++;
            }
        }
        return result;
    }
}

나의 코드

---

소요 시간: 45분
시간 복잡도: $O(right - left + 1)$

---

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] result = new int[(int)(right - left) + 1];

        int share = (int)(left / n);
        int remain = (int)(left % n);
        
        for (int i = 0; i < (int)(right - left) + 1; i++) {
            result[i] = Math.max(share, remain) + 1;
            if (remain == n - 1) {
                share++;
                remain = 0;
            }
            else {
                remain++;
            }
        }
        return result;
    }
}

AI 코드

---

코드 해석

전반적인 알고리즘은 동일하지만,
if/else문을 제거하고,
매 반복마다 (int)(right - left + 1)을 계산하는 과정을 없앰

---

시간 복잡도: $O(right - left + 1)$

---

class Solution {
    public int[] solution(int n, long left, long right) {
        int len = (int)(right - left + 1);
        int[] result = new int[len];

        for (int i = 0; i < len; i++) {
            long pos = left + i;
            long row = pos / n;
            long col = pos % n;
            result[i] = (int)(Math.max(row, col) + 1);
        }
        return result;
    }
}

문제 풀이 후기

이전에 막혔던 부분을 이번 복습을 통해 해결했다.
앞으로 한 발짝 나가는 기분이 들면서 스스로 성장했다는 것을 느낄 수 있었다.

문제를 해결하는 과정에 있어서 수학적인 규칙을 찾는 것 만큼
문제를 효율적으로 풀 수 있는 방법이 없다는 생각이 들었다.

AI의 개선 코드를 통해
이와 같은 사소한 부분까지 효율적으로 분석할 수 있어야 겠다는 생각이 들었다.