[PS] 99클럽 코테 스터디 1일차 TIL (n^2 배열 자르기)

문제

문제 링크

풀이

첫번째 풀이 (메모리 초과)

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

class Solution {
    public int[] solution(int n, long left, long right) {
        
        // 1. 2차원 배열에 값 세팅
        int[][] arr = new int[n][n];
        for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= n; j++) {
            arr[i - 1][j - 1] = Math.max(j, i);
          }
        }

        // 2. 2차원 배열 -> 1차원 배열
        int[] tmp = new int[arr.length * arr[0].length];
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < n; j++) {
            tmp[arr[i].length * i + j] = arr[i][j];
          }
        }

        // 3. 인덱스 범위만 가져오기
        int[] result = Arrays.copyOfRange(tmp, (int) left, (int) right + 1);


        return result;
    
    }
}

처음 작성한 코드는 메모리 초과로 통과하지 못했다. 간략하게 코드를 설명하자면,

1번 주석에서, 배열을 만들어 n = 1 ~ n 의 모든 값을 저장한다. 이때, 행과 열의 인덱스를 비교해 둘 중 큰 값을 넣는다. arr 배열에는 아래 처럼 들어가는 것을 확인할 수 있다.

// n = 3
[[1, 2, 3], [2, 2, 3], [3, 3, 3]]

// n = 4
[[1, 2, 3, 4], [2, 2, 3, 4], [3, 3, 3, 4], [4, 4, 4, 4]]

2번 주석에서, 문제에서 요구하는 것처럼 2차원 배열을 1차원 배열로 합친다. 1차원 배열의 길이는 2차원 배열의 행의 길이 * 각 열의 길이 로 설정할 수 있다. 값 인덱스에 들어가야 할 값을 살펴보면 아래와 같은 규칙이 있다.

// n 이 4일때
tmp[4] = arr[1][0]
tmp[5] = arr[1][1]
tmp[6] = arr[1][2]
tmp[7] = arr[1][3]
  ...

// 4 = n * 1 + 0
// 5 = n * 1 + 1
// 6 = n * 1 + 2
// 7 = n * 1 + 3
  ...
// x = n * i + j

3번 주석에서, 문제에서 요구하는 left 부터 right 범위를 가져오기 위해 Arrays.copyOfRange() 를 사용했다.

그러나 이 코드는 실행하면 메모리 초과가 나온다. 문제에서 n 의 범위가 10^7 이기 때문에 1번 주석에서 10^7 * 10^7 이 되어 무려 100조번 계산해야 한다. 이를 위와 같이 O(n^2) 로 풀게되면 대략 100만초가 걸린다… (1초에 10^8 번 연산한다고 가정.)

두번째 풀이

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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;
          int row = (int) (pos / n);
          int col = (int) (pos % n);
          result[i] = Math.max(row, col) + 1;
        }


        return result;
    
    }
}

일단 첫번째 풀이에서 이중 for 문을 없애야 한다. 결국 2차원 배열에 값을 세팅하는 과정을 건너뛰고 바로 결과 배열을 출력해야 한다는 뜻이다.

// n = 4, left = 7 일때
result[7] = 4     // (7 + 0) / 4 = 1...3
result[8] = 3     // (7 + 1) / 4 = 2...0
result[9] = 3     // (7 + 2) / 4 = 2...1
result[10] = 3    // (7 + 3) / 4 = 2...2
result[11] = 4    // (7 + 4) / 4 = 2...3
  ...

// result[x] = (/ 연산) or (% 연산) 결과 중 큰 값 + 1

사실 문제에서 n 의 범위 조건만 확인해도 어떻게 풀어야 될지 감을 잡을 수 있었을 텐데, 시간복잡도 계산을 하는 것이 익숙하지 않아서 항상 이렇게 틀리고 나서 수정하곤 하는데.. 시간복잡도의 종류나 대략적인 계산 방법 등을 좀 더 학습해야 할 것 같다.