[Programmers] n^2 배열 자르기

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

프로그래머스

문제 설명

프로그래머스 문제 페이지에서 이해하기 쉽도록 gif를 제공한다. 아래가 입출력 1번에 대한 설명이다.

 

처음엔 문제에서 주어진대로 배열을 활용하여 해결하려고 했다. 문제는 1차원 배열의 크기가 n*n이 되어야 하는데 n은 최대 10,000,000이다. 즉 arr의 최대 크기는 10,000,000의 제곱(1조)가 된다. 코드를 쓰면서도 배열 크기가 1조짜리인 적은 안 될 거라고 생각했다. 실행을 돌려보니 역시나 메모리 초과 오류가 발생했다. 배열이 아니면 ArrayList같은 자료구조를 사용해야 하는데 이 역시 결국 같은 맥락으로 시간 초과와 같은 에러가 발생할 거라고 생각했다. 그래서 이건 공식이 있을거라 생각했고 질문을 살펴보니 역시 맞았다.

첫 번째 입력을 가지고 분석해보자. 첫 번째 입력을 1차원 배열로 쭉 폈을 때는 [1, 2, 2, 2, 3, 3, 3, 3, 3]이 된다. 각 요소의 2차원 배열에서의 위치는 [1, 1], [1, 2], [2, 1], [2, 2], [1, 3], [2, 3], [3, 1], [3, 2], [3, 3] 이다. 뭔가 보이지 않나? 각 위치의 값은 행과 열의 값 중 더 큰 값이 된다. 그러면 1차원 배열에서 행과 열의 값을 구할 수 있으면 이 문제를 해결할 수 있겠다. 행과 열은 나누기와 나머지 연산을 통해 구할 수 있다. 왜냐하면 2차원 배열을 1차원 배열로 쭉 나열할 것이기 때문에 행의 값은 요소들을 n으로 나눈 몫이 되는 것이고 열 값은 나머지 값이 된다. 예를 들어 2번째 값에 대한 행과 열을 구하려면 행은 2 / 3, 열은 2 % 3이 된다. 이를 활용하면 n*n과 같은 엄청나게 큰 배열을 만들지 않고도 문제를 해결할 수 있다.

코드

class Solution {
    public int[] solution(int n, long left, long right) {
        int[] result = new int[(int)(right - left) + 1];
        
        for (int i = 0; left <= right; i++, left++) {
            int row = (int)(left / n) + 1;
            int col = (int)(left % n) + 1;
            result[i] = Math.max(row, col);
        }
        
        return result;
    }
}