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

🔒 2단계 - n^2배열 자르기

입출력 예시

📌 테스트케이스 추가 힌트

해당 문제는 gif 설명이 잘 되어 있어, 추가 테스트 케이스가 필요하지 않았다.

❌ 풀이법 #메모리 초과 실패

해당 문제는 알고리즘을 생각 할 필요 없이, 애니메이션으로 잘 보여주고 있기 때문에
입출력 예시를 그대로 코드로 옮겼다.

하지만, 공간복잡도와 시간 복잡도를 생각하지 않는 방법이기 때문에 메모리 초과 실패와
시간초과 실패를 겪었다.

❌ 풀이 #메모리 초과 실패

import java.util.*;

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

        List<List<Integer>> rows = new ArrayList<>();

        for(int row=1; row<=n; row++){
            List<Integer> columns = new ArrayList<>();

            for(int column=1; column<=n; column++){

                if(column<row){
                    columns.add(row);
                }else{
                    columns.add(column);
                }
            }
            rows.add(columns);
        }

       // System.out.println(rows);


        List<Integer> connect = new ArrayList<>();

        for(List<Integer> row : rows){
            connect.addAll(row);
        }

        for(int j=0; j<answer.length; j++){
            answer[j] = connect.get(j+(int)left);
        }


        return answer;
    }
}

단순히 입출력 예시에서 나온 gif를 코드로 옮기면, 메모리 초과와 시간 초과 실패가 뜨게 된다.

✍️ 풀이법

문제를 풀 수 있는 다른 방법이 필요했고, 사각형을 전부 그리지 않고 답만 도출해 내는
코드로 변경하였다.

 해당 문제를 풀 때, answer에 들어가는 [left ~ right] 값이 뭐가 들어가야하는 지, 먼저 그림으로
 이해한 다음. 규칙을 찾으면서 풀었다.


위 그림의 index 값을 주어진 n 값으로 나누면 열(row) 보다 1 적은 값이 도출된다.
이 점을 이용하여, index/n+1 = row로 식을 세우고, 행(columns)의 값이 열보다 
작다면 row 값으로 변경해 주었다.

🗝️ 풀이

import java.util.*;

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

        for(int i=0; i<answer.length; i++){
            row = (left+i)/n +1;
            columns = (left+i)%n +1;

            if(row < columns){
                answer[i] = (int)columns;
            }else{
                answer[i] = (int)row;
            }
        }
        return answer;
    }
}