[프로그래머스] 레벨2 n² 배열 자르기

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

프로그래머스

 

사실 맨 처음 접근방법은 2차원의 배열을 전부 다 만들고 부분 배열로 잘라서 결과를 리턴하는 방식이었다. 하지만 메모리 초과가 뜨고 정확도가 35점이 나온 걸 보고 다른 방법을 생각해봐야만 했다.

두 번이나 실패한 후에 문제를 해결할 수가 있었는데 일단 중간 접근방법은 배열이 만들어지는 규칙을 찾아 ArrayList에 넣는 방법이었다. 중간에 break문을 걸어 최대한 시간/공간복잡도를 낮추려고 했었는데 이렇게 해도 55점 밖에 안 나오는 것을 봐서는 아무래도 이중 for문을 쓰는 문제가 아니라는 생각이 들었다.

그래서 수학적인 규칙성을 찾기 위해서 배열의 인덱스와 값을 나열해 보았는데, 여기서 해결 방법을 찾을 수 있었다. 일단 직접적으로 배열값을 계산해서 구할 필요가 없었으며, 해당 위치의 행과 열의 인덱스 중 더 큰 값이 배열값으로 들어간다는 규칙을 도출할 수 있었다. 그리고 주의할 것은 숫자의 자리 수이므로 변수 선언이나 사용을 할 때 전부 Long 형태로 계산하여 해결할 수 있었다.

---

문제 및 입출력

---

코드(부분정답, 메모리초과 발생)

import java.util.ArrayList;

class Solution
{
    public Object[] solution(int n, long left, long right)
    {
        ArrayList<Integer> answer = new ArrayList<Integer>();
        
        for(int i=1; i<=n; i++)
        {
            if(answer.size()>right)
            {
                break;
            }
            if(i==1)
            {
                for(int j=1; j<=n; j++)
                {
                    answer.add(j);
                }
            }
            else if(i==n)
            {
                for(int j=1; j<=n; j++)
                {
                    answer.add(i);
                }
            }
            else
            {
                for(int j=1; j<=i; j++)
                {
                    answer.add(i);
                }
                for(int j=i+1; j<=n; j++)
                {
                    answer.add(j);
                }
            }
        }
        
        return answer.subList((int)left, (int)right+1).toArray();
    }
}

---

코드(정답)

import java.util.ArrayList;

class Solution
{
    public Object[] solution(int n, long left, long right)
    {
        ArrayList<Long> answer = new ArrayList<Long>();
        
        if(n==1)
        {
            return new Object[]{1};
        }
        for(long i=left; i<=right; i++)
        {
            long row = i/n;
            long col = i%n;
            answer.add(Math.max(row, col)+1);
        }
        
        return answer.toArray();
    }
}