[프로그래머스] n^2 배열 자르기 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

정수 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 함수를 완성해주세요.

2. 입력

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

3. 예제

n	left	right	result
3	2	5	3, 2, 2, 3
4	7	14	4, 3, 3, 3, 4, 4, 4, 4

4. 풀이

이번 문제는 문제에서 주어진 방법대로 2차원 배열을 만들어 해당 각각의 cell에 해당하는 수를 담아 두려는 접근으로 시작하면 메모리 초과라는 결과를 받게 된다. 입력 제한 사항으로 n 값은 최대 10^7이기에 2차원 배열로 선언하게 되면 10^7 * 10^7이라는 어마어마한 2차원 배열이 생성되게 된다.

 

그럼 이번에는 2차원 배열을 선언하지 않고 2 중첩 반복문 안에서 left와 right의 값들을 구해 컬렉션에 입력을 하는 방법으로 구현하면 이번에는 시간 초과라는 결과를 받게 된다. 이것 또한 위와 동일하게 10^7 * 10^7의 반복을 수행하기 때문에 시간이 오래 걸리는 것이다.

 

이제 위 두 풀이 접근의 문제 점들을 파악했다. 위 과정을 정리하면 입력 n * n만큼의 배열을 만들지 않고 n * n만큼의 반복을 수행하지 않는 방법으로 문제를 해결해야 된다.

 

먼저 4 * 4 배열을 그리면 아래 표와 같은 값들로 입력된 배열이 완성된다.

1	2	3	4
2	2	3	4
3	3	3	4
4	4	4	4

여기서 보면 세로 Index를 i로 보고 가로 Index를 j로 본다면 i보다 j가 작거나 같은 경우 i+1의 값이 된다는 것을 알 수 있다.

 

예로 들어보면 세로의 Index 2의 경우 가로 Index 0, 1, 2는 모두 3이 된다.

1	2	3	4
2	2	3	4
3	3	3	4
4	4	4	4

 

이번에는 i보다 j가 큰 경우를 살펴보면 j+1이 된다는 것을 알 수 있다.

 

예로 들어보면 세로의 Index 2의 경우 가로 Index 3는 4가 되고 세로의 Index 1의 경우 가로 Index 2는 3이 가로 Index 3는 4가 된다. 

 

이제 가로와 세로의 규칙을 찾았다 그러면 시작(left) 위치부터 종료(right) 위치 사의 숫자들로 2차원 배열에 해당하는 값을 찾을 수만 있다면 값을 담는 2차원 배열은 생성하지 않고 반복문 또한 시작(left)에서 종료(right)까지 반복하면 정답을 찾을 수 있다.

 

문제에서 주어진 배열의 순서를 보면 0부터 시작하여 오른쪽으로 한 칸 옮기면 1씩 증가하는 식으로 되었다.

 

해당 부분을 표로 그린다면 아래 표와 같이 될 것이다.

0	1	2
3	4	5
6	7	8

 

그럼 세로 Index를 구해보자면 순서에 n을 나눈 값이 된다.

 

이유는 가로 또한 n만큼 있기 때문에 n의 개수를 넘으면 한 칸 아래의 Cell부터 순서가 입력되기 때문이다.

 

즉 n의 배수인 경우는 2차원 배열의 가장 왼쪽에 존재하며 몫의 Index에 존재하게 된다.

 

가로 Index의 경우는 순서에 n을 나눈 나머지가 된다.

 

이유는 위의 세로 Index로 해당 순서의 세로 Index의 가장 왼쪽의 위치를 알 수 있게 되었다. 그다음은 해당 순서는 나머지만큼 왼쪽에서 떨어져 있기 때문이다.

 

자 그럼 이제 순서의 i와 j를 모두 구할 수 있게 되었다.

 

이제 시작점부터 종료점까지 순서를 n으로 나눈 값이 i이고 나머지가 j가 되므로 i보다 j가 작거나 같은 경우 i+1을 i보다 j가 큰 경우는 j+1을 추가하여 정답을 구하면 된다.

 

위 과정에서 한번 더 코드를 줄이려면 몫과 나머지 중 큰 값에 1을 더한 값이 정답이 된다는 것을 알 수 있다.

 

5. 코드

전체 코드는 Git에 있습니다.

List<Long> answer = new ArrayList<>();

for (long i = left; i <= right; i++)
	answer.add(Math.max(i % n, i / n) + 1);

return answer.stream().mapToInt(Long::intValue).toArray();