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

🔗 문제 링크

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

🤔 문제

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

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

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

📌 제한사항

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

😮 문제 해결 방법

문제 제한사항을 보면 배열 주어지는 배열 행 과 열 최대가 $10^7$이고 주어지는 left 와 right 가 10 ^ 14 까지 주어질 수 있다.

하지만 right - left 가 $10^5$ 보다 작은 제한 사항인 걸로 보아 굳이 2차원 배열을 생성하지 않고도 (right - left) 만큼 반복하여 해답을 구할 수 있음을 유추할 수 있다.

n = 4, left = 8, right = 14인 입력 예제를 예로 규칙을 찾아보면

2차원 배열을 잘라 1차원 배열로 생성하면 [1,2,3,4,2,2,3,4,3,3,3,4,4,4,4] 가 된다.

여기서 규칙을 찾아보면, 찾고자 하는 인덱스를 n 으로 나눈 몫과 나머지 중 큰 값에 + 1을 해주면 답을 얻을 수 있다.

1. index / n ≥ index % n → index / n + 1
2. index / n < index % n → index % n +1

마지막으로 주의할 점은, long 값으로 들어오기 때문에 int 값으로 캐스팅을 해줘야 한다는 점이다.

🚩 Java 코드

package com.algorithm.Programmers.Lv2;

public class Solution_87390_n2_배열_자르기 {
    public static void main(String[] args) {
        int n = 4;
        int left = 7;
        int right = 14;
        int[] solution = solution(n, left, right);
        for(long x : solution) System.out.println("x = " + x);
    }

    private static int[] solution(int n, int left, int right) {
        int size = (int) (right - left) + 1;
        int[] answer = new int[size];

        // 조건 : target / n < target % n ->  (target % n) + 1;
        // 조건 : target / n >= target % n -> (target / n + 1)

        int loop  = 0;
        for(long target = left; target <= right; target++) {
            long rowIdx = target / n;
            long colIdx = target % n;
            if(rowIdx < colIdx) answer[loop] = (int) colIdx + 1;
            else answer[loop] = (int) rowIdx  + 1;
            loop++;
        }
        return answer;
    }
}