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

이 문제를 해결하는데 이틀이 걸렸다.

별생각 없이 문제를 읽으면 어렵지 않을 것 같은데 함정이 난무한다....

나는 함정카드에 모두 걸려서 리팩터링 하느라 한 번에 해결하지 못하고 이틀에 걸쳐 생각해서 풀었다.

 

문제에 친절하게 애니메이션으로 어떻게 구현해야 할지 알려준다.

근데 이 애니메이션이 바로 첫 번째 함정카드다.

n의 크기가 매우 클수도 있기 때문에 애니메이션처럼 2차원 배열을 n만큼 선언하면 바로 메모리 초과가 난다.

대부분의 테스트 케이스는 메모리 초과, 그리고 몇 개의 케이스는 시간 초과가 난다.

 

그러면 애니메이션 2번째 그림처럼 처음부터 1차원 배열로 만들어야겠다는 생각이 들었는데 이것도 함정카드다.

생각대로면 int[] arr = new int[n * n]으로 만들어야 하는데 이것도 메모리 초과가 난다.

 

그러면... subString이나 subList를 이용해야 하나? 생각이 들었는데 이것도 함정카드다.

left와 right도 long으로 주어지고 있어 subString이나 subList 사용을 못한다.

 

여기서 두 가지 방법을 생각했다.

첫 번째는 배열을 만들면 안 되고 left와 right 인덱스 사이의 값을 바로 구하는 방법

두 번째는 메모리 초과를 해결하고 최적화하는 방법

 

그런데 첫 번째 방법은 어떻게 해야 할지 생각이 안 났다.

그래서 일단 두 번째 방법으로 시도했는데 메모리 초과는 나지 않았지만 시간 초과는 여전했다.

당연한 게 일단 로직이 엄청 복잡하고 for문의 depth도 깊고 많다....

 

여기서 최적화를 하는 방법은 더 어려울 것 같아서 잠시 쉬는 시간을 가지고 다시 풀어보았다.

그런데 우연히 2차원 배열을 좌표로 생각하면 어떨까 라는 생각이 들어서 자세히 보니 규칙을 발견했고

정말 간단하게 풀렸다.

 

로직은 행렬의 값은 Max(행 번호, 열 번호) 라는게 끝이다.

i를 left부터 right까지 설정하고 행 번호와 열 번호만 알면 되는데 행 번호는 i / n이고, 열 번호는 i % n이다.

고생했던 것에 비해 너무 쉽게 풀려서 좀 허무했지만, 생각을 많이 할 수 있었던 문제였다.

---

.

실패 코드 (시간 초과)

import java.util.*;
class Solution {
    public int[] solution(int n, long left, long right) {
        long leftIdx = left / n;
        long leftRest = left % n;
        long rightIdx = right / n;
        long rightRest = right % n;
    
        List<Integer> result = new ArrayList<>();
         for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>();
            if (i == 0) {
                int cnt = 1;
                for (int j = 0; j < n; j++) {
                    list.add(cnt++);
                }
            } else {
                int temp = i + 1;
                for (int j = 0; j < temp; j++) {
                    list.add(temp);
                }
                if (temp < n) {
                    int temp2 = 1;
                    for (int j = temp; j < n; j++) {
                        list.add(temp + temp2++);
                    }
                }
            }
              if (i == leftIdx) {
                for (int j = (int) leftRest; j < list.size(); j++) {
                    result.add(list.get(j));
                }
            } else if(i > leftIdx && i < rightIdx) {
                for (int j = 0; j < list.size(); j++) {
                    result.add(list.get(j));
                }
            } else if(i == rightIdx) {
                for (int j = 0; j <= rightRest; j++) {
                    result.add(list.get(j));
                }
            }
         }
         int[] answer = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            answer[i] = result.get(i);
        }
        return answer;
    }
}

 

최종 코드

import java.util.*;
class Solution {
    public int[] solution(int n, long left, long right) {
        // 값을 저장할 list
        List<Long> list = new ArrayList<>();

        // Max(행, 열)이 값
        for (long i = left; i <= right; i++) {
            list.add(Math.max(i / n, i % n) + 1);
        }

        // list answer 배열에 복사
        int[] answer = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            answer[i] = Math.toIntExact(list.get(i));
        }
        return answer;
    }
}