[JAVA] n^2 배열 자르기

< 처음 풀이 > 

import java.util.*;
class Solution {
    public int[] solution(int n, long left, long right) {
        int arr[][]=new int[n][n];
        
        // 2차원 배열에 값 넣기 
        int num=1;
        while(num<=n){
          for(int i=0;i<num;i++){
              for(int j=0;j<num;j++){
                  if(arr[i][j]==0)
                      arr[i][j]=num;
              }
          }
          num++;
        }
        
        // 2차원 배열 값을 1차원 배열에 넣기 
        int new_arr[]=new int[n*n];
        int index=0;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                int k=arr[i][j];
                new_arr[index]=k;
                index++;
            }
        }
    
        int[] answer = new int[(int)(right-left+1)];
        
        int index2=0;
        for(int i=(int)left;i<=(int)right;i++){
            answer[index2]=new_arr[i];
            index2++;
        }
        return answer;
    }
}

 

 처음의 나는 정말 정직하게 문제에서 요구하는 그대로 2차원 배열에 값을 넣고, 이것을 1차원 배열로 바꾸고 답을 찾으려고 했다. 이렇게 하니 메모리 초과로 계속 실패를 했다. 프로그래머스 질문하기에 보니 아래와 같은 답변이 있었다. 내가 너무 문제를 무식하게 풀고 있었다는 걸 깨달았다. 

 

 

< 풀이 >

import java.util.*;
class Solution {
    public  List<Long> solution(int n, long left, long right) {
        
        List<Long> list = new ArrayList<>();
        
        for(long i=left;i<right+1;i++){
             list.add(Math.max(i/n,i%n) + 1);
        }
        
        return list;
    }
}

 

위의 배열에는 이와 같은 규칙이 있다. 따라서 배열에 값을 다 넣고 그 값을 찾는 형식이 아니라, left와 right 사이의 값만 구해서 답을 구하는 형식으로 하면 메모리 초과가 나지 않는다. 

 

✍🏻 느낀점

 

문제를 풀기 전에 제한사항을 잘 봐야겠다는 생각이 들었다. 문제의 답만 맞추려고 하는 것이 아니라 어떻게 하면 문제를 효율적으로 풀 수 있을지를 생각하는 것도 중요한 부분인 것 같다. 뭔가 위의 방법처럼 저렇게 규칙을 찾으려고는 하지 않았는데, 이번에 또 하나 배웠다 ! 

 

 

 

 

 

 

 

 

 

 

 

참고 블로그

---

https://taehoung0102.tistory.com/93#google_vignette