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

문제내용

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

프로그래머스

정수 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

---

문제풀이

첫풀이는 문제에서 주어진대로 2차원 배열 생성후 값을채우고 1차원 배열로 다시 만든다음 left~rigth까지 배열을 잘라서 반환하도록 풀었는데 이렇게 풀면 메모리 초과가 난다.

n의 최대 값은 n^7이기 때문에 1차원 배열로 모든값을 넣었을때 최악의 경우 n^14 길이인 배열을 만들어야한다. 따라서 int형 배열로는 left~rigth까지 선택해서 반환되는 배열을 만드는게 불가능해진다.

이런 이유때문에 2차원배열을 만들지말고 처음부터 left~rigth까지(right - left < 10^5) 값들을 갖고와서 int형배열에 요소를 넣어주는게 필요하다.

이때 필요한건 배열에서 나오는 값들의 규칙이다. 아래 표를 보자

 

	0	1	2
0	1(0번째)	2(1번째)	3(2번째)
1	2(3번째)	2(4번째)	3(5번째)
2	3(6번째)	3(7번째)	3(8번째)

첫번째 줄과 칸은 행열의 인덱스를 나타내고, 그외의 숫자는 i행 j열의 요소값을 나타낸다.

요소값 옆에 있는 괄호안에 숫자는 1차원 배열로 만들었을때 나오는 인덱스 값이다.

 

이 표를 보면 한가지 규칙을 알수 있다.

1행2열의 값은 3  -> Math.max(행, 열) + 1 -> Math.max(1, 2) +1 = 3 

2행1열의 값은 3  -> Math.max(행, 열) + 1 -> Math.max(2, 1) +1 = 3

이라는걸 알수 있다. 

즉, 2차원 배열에 채워지는 요소값은 Math.max(행, 열) + 1 이라는 규칙이 나온다.

 

그럼 괄호안에 적혀있는 i번째 일때 요소값을 구하려고 한다면, i번째 일때 행과 열의 인덱스가 뭔지만 알면된다.

5번째 값은 3 -> 행: 5/n , 열: 5%n -> 행: 5/3 , 열: 5%3 -> Math.max(5/3, 5%3) + 1

7번째 값은 3 -> 행: 7/n , 열: 7%n -> 행: 7/3 , 열: 7%3 -> Math.max(7/3, 7%3) + 1

즉, i번째 일때 값은 Math(행, 열) + 1 == Math.max(i/n , i%n) + 1 과 같은 말이 된다.

 

이를 이용하면 left~rigth까지 for문 한번으로 문제를 풀 수 있다.

---

코드

public class Solution {
    public static int[] solution(int n, long left, long right) {
    	int[] answer = new int[(int)(right-left)+1];
    	int idx=0;
    	for(long i=left; i<=right; i++) {
    		long val = Math.max(i/n, i%n)+1; // Math.max(행, 열) + 1
    		answer[idx++] = (int)val;
    	}
    	return answer;
    }
    
}

---

마치며

코드는 짧고 쉽다. 하지만 일반적으로 구현하면 안되고, 주어진 값들을 가지고 규칙을 찾아내서 구현해야 한다는점이 어려운 점이라고 생각된다. 주어진걸 어떻게 활용해야할지 생각해보는 훈련이 필요하다.