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

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

코딩테스트 연습 - n^2 배열 자르기

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

        int indexAnswer = 0;

        for (long i = left / n; ++i <= n;)
        {
            if (indexAnswer == answer.Length)
                break;

            long index = 0;
            if (i == left / n + 1)
                index = left % n;

            for (long j = index; ++j <= n;)
            {
                int num = (int)j;
                if (num < (int)i)
                    num = (int)i;

                answer[indexAnswer++] = num;
                if (indexAnswer == answer.Length)
                    break;
            }
        }

        return answer;
    }
}

문제의 규칙은 생각보다 이해하기 쉽고 

 

제한사항

• 1 ≤ n ≤ 107
• 0 ≤ left ≤ right < n2
• right - left < 105

요 제한사항을 잘 봐야 하는데 n의 범위가 심상치가 않다.

반복문을 어떻게 돌리냐가 중요한데 이유는

이런 차이가 생긴다..

왼쪽은 처음부터 끝까지 배열을 쭉 돌아서 푸는 방식이고

오른쪽은 반복문을 돌 때 문제에서 주어지는 배열의 범위인 left, right사이의 범위만 돌아서 푼 것

public class Solution
{
    public int[] solution(int n, long left, long right)
    {
        // 필요한 크기만큼만
        int[] answer = new int[right - left + 1];

        int indexAnswer = 0;

        // 규칙 이해하면 시작 index의 이유를 알 수 있음
        for (long i = left / n; ++i <= n;)
        {
            // 이미 answer 크기를 지정함 -> right 신경 쓸 필요 없이
            // 답이 다 차면 걍 break
            if (indexAnswer == answer.Length)
                break;

            // 첫 반복문을 돌 때만 left % n을 넘겨주면
            // 정확하게 left로 나눈 부분으로 들어가지니까
            long index = 0;
            if (i == left / n + 1)
                index = left % n;
            
            for (long j = index; ++j <= n;)
            {
                // 규칙상
                int num = (int)j;
                if (num < (int)i)
                    num = (int)i;

                answer[indexAnswer++] = num;
                
                // 여기도 마찬가지로 답이 다 차면 걍 break
                if (indexAnswer == answer.Length)
                    break;
            }
        }

        return answer;
    }
}