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

문제 설명

 

프로그래머스

 

접근 방법

처음 접근했었던 방법은 2차원 배열을 생성한 후 해당 2차원 배열로부터 left ~ right 길이의 1차원 배열을 잘라내어 이를 반환하는 것이었습니다. 하지만 인자로 주어지는 n의 최대값은 10의 7승으로 n * n 2차원 배열을 만드는 순간 Outofmemoryerror 에러가 발생하게 됩니다. 즉, 주어진 n에 대해서 2차원 배열을 만드는 게 아니라 left와 right 범위에 해당되는 배열만을 추려낼 필요가 있었습니다.

 

이때, 문제에서 2차원 배열의 값을 채우는 방법에는 일종의 규칙성이 있었는데, 바로 행 인덱스과 열 인덱스 중 가장 큰 값에 + 1을 한 값이 해당 배열 요소의 값으로 들어간다는 점이었습니다.

 

 

문제에서는 left와 right라는 2차원 배열의 특정 구간에 대한 양 끝 지점을 인자로 제공하고있습니다. 이 값을 n으로 / 연산과 % 연산한다면 행과 열에 대한 인덱스 값을 구할 수 있는데, 이 값을 통해 배열의 값을 추려낼 수 있습니다.

 

이때 저 같은 경우에는 left와 right 사이에 구간만큼 2차원 배열을 만든 후 다시 이 사이의 길이만큼 1차원 배열을 만들어 복사하였는데, 이러한 방식은 소스 코드도 길어질 뿐만 아니라 불필요한 메모리 및 시간을 낭비하게 됩니다.

 

문제를 해결한 후 프로그래머스에 모범 소스 코드를 참고하였는데, 아래와 같이 단순히 스트림을 이용하여 left와 right 사이의 정수(Long) 스트림을 이용하여 / n 연산과 % 연산을 해나간다면 1차원 배열로 간단하게 변환시킬 수 있었습니다.

 

import java.util.Arrays;
import java.util.stream.LongStream;

class Solution {
    public int[] solution(int n, long left, long right) {
        return LongStream.rangeClosed(left, right)
        .mapToInt(value -> (int) (Math.max(value / n, value % n) + 1))
        .toArray();
    }
}

 

나의 소스 코드

class Solution {

    public int[] solution(int n, long left, long right) {
        int startRow = (int) (left / n), startCol = (int) (left % n), endRow = (int) (right / n), endCol = (int) (right % n);

        int[][] arr;

        if (startRow == endRow) {
            int[] result = new int[endCol - startCol + 1];
            for (int i = startCol, index = 0; i <= endCol; i++, index++) {
                result[index] = Math.max(startRow, i) + 1;
            }

            return result;
        }

        arr = new int[endRow - startRow + 1][n];

        for (int i = 0; i < endRow - startRow + 1; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = Math.max(i + startRow, j) + 1;
            }
        }

        int[] result = new int[(int) (right - left) + 1];
        int index = 0;
        for (int col = startCol; col < n; col++) {
            result[index++] = arr[0][col];
        }

        for (int i = 1; i < endRow - startRow; i++) {
            for (int j = 0; j < n; j++) {
                result[index++] = arr[i][j];
            }
        }

        for (int i = 0; i <= endCol; i++) {
            result[index++] = arr[endRow - startRow][i];
        }

        return result;
    }
}

 

참고자료

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