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

문제 링크 -> https://programmers.co.kr/learn/courses/30/lessons/87390

코딩테스트 연습 - 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

------------------------------------------------------------풀이------------------------------------------------------------------
- left부터 right까지 1번씩 돌면서 해당 index의 value를 구한다. 

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray = (left..right).map{
        val x = it/n; val y = it%n;
        if(y <= x) (x+1).toInt()
        else (y+1).toInt()
    }.toIntArray()
}

주의사항 
 - left와 right의 값은 n^2안에 있지만 n의 범위에서 ^2을 해보면 Int값을 훨씬 초과한다. 그렇기에 주어진 방식대로 n*n행렬을 만들어 일렬로 배치한 후 배열을 자르게되면 n의 값이 클 경우 시간이 초과된다. 

아래는 주의사항을 생각하지 않고 작성한 코드 

class Solutiona {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        var answer = ArrayList<Int>()

        for( i in 0..n-1){
            for( j in 0..n-1){
                if( i*n+j >= left && i*n+j <= right ){
                    if( j <= i) {
                        answer.add(i+1)
                    }
                    else {
                        answer.add(j+1)
                    }
                }
            }
        }
        return answer.toIntArray()
    }
}

일렬로 배치해서 자르지는 않지만, left~right이외의 필요없는 부분도 반복문으로 확인하므로 시간이 초과된다. 

위 코드로 실패를 맛보고 다른 방법을 생각했다. 아래 행렬에서 규칙을 찾아야 한다. 

- 노란색으로 표시된 부분으로 범위를 나누면 쪽의 값들은 (x, y)일 때 x+1의 값이고 왼쪽은 (y+1)의 값이다.
즉 i <= j면 i+1 아니면 j+1로 처리하면 된다.
- 그럼 for( i in left..right)에서 i값으로 x와 y를 유츄하면   i<left, i>right의 경우는 구하지 않아도된다.

8부터 15까지 자르라고 했다고 가정하자. 그럼 아래 그림이 범위가 된다. 

- 5*5행렬을 일렬로 붙였을 때 8번 index의 x,y는 1과 3이다. 
- 9번 index의 x, y는 1과 4 이다.
- 15번 index의 x, y는 3,0이다. 
즉 n번 index의 x와 y는 index/n, index%n이다.

위를 토대로 코드를 짜면 첫 번째로 게시한 코드가 탄생한다.

------------------------------------------------------------결과------------------------------------------------------------------

- 문제에 대한 질문 댓글 환영!
- 중간에 잘못된 부분이 있다면 댓글로 남겨주세요. 수정하겠습니다.