[JAVA , Lv.2] n^2 배열 자르기

[문제]

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

프로그래머스

---

[제한사항]

• 1 ≤ n ≤ 10^7
• 0 ≤ left ≤ right < n^2
• right - left < 10^5

---

[내 풀이]

import java.util.*;

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

        for(int i=0; i<answer.length; i++){
            int a = (int)(left/n)+1;
            int b = (int)(left%n)+1;
            left++;
            answer[i] = Math.max(a,b);
        }

        return answer;
    }
}

---

[풀이 과정]

좀 골치아픈 문제였다.

제한사항으로 주어진 숫자의 범위가 매우매우 크다보니 메모리 초과도 쉽게나서 코드를 굉장히 신경써서 짜야했다.

내가 풀어나갔던 과정은

1. (실패)주어진 문제대로 n*n의 2차원 배열을 만들어 값을 삽입한 후 Left와 Right사이의 값만을 answer배열에 넣었다.

    (이유) n값이 최대 10^7까지 주어질 수 있어서 이만큼의 배열을 만들게되면 배열이 커져서 메모리 초과가 일어난다.

 

2. (실패)cnt를 활용하여 for문을 돌면서 cnt의 값이 left와 right사이에 있을 때만 배열에 추가하도록하였다.

    (이유, 추정) 어찌되었건 방법1처럼 직접 배열을 메모리 초과할만큼 생성하진 않지만 for문을 굉장히 많이 돌기 때문에 런타임에러가 났다.

 

3. (성공) 위의 코드이다.