프로그래머스 - n^2 배열 자르기(Java, 자바)

문제 링크

문제 설명

정수 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⁷
• 0 ≤ left ≤ right < n²
• right - left < 10⁵

---

입출력 예

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

 

---

입출력 예 설명

입출력 예 #1

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

입출력 예 #2

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

---

문제 풀이 방법

이 문제는 문제 예시처럼 풀면 초과로 인해 해결이 불가하다.
애니메이션 보자마자 바로 든 생각은 배열에 규칙에 맞게 값들을 넣은 다음 left, right 범위에 맞게 잘라서 출력하면 된다고 생각했다.

위와 같은 배열이 있다고 가정 해보자.
숫자 밑에 있는 괄호가 배열의 인덱스이다.
여기서 한가지 규칙을 찾을 수 있다.
배열의 값은 배열 인덱스에서 큰 값 + 1 한 값이 배열 원소 값이 된다.

int row = (int)((i + left) / n) + 1;
int col = (int)((i + left) % n) + 1;

배열 원소 값의 규칙을 찾았으면, 배열 row, col의 값을 구해야한다.
row, col 의 값은 위의 식으로 구할 수 있다.

---

전체 코드

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 row = (int)((i + left) / n) + 1;
            int col = (int)((i + left) % n) + 1;
            answer[i] = Math.max(row, col);
        }
        return answer;
    }
}