n^2 배열 자르기(Lv.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 ≤ 107
• 0 ≤ left ≤ right < n2
• right - left < 105

입출력 예

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차원 배열을 만드는 과정을 나타낸 것입니다.

---

풀이

n번째 배열까지 만든다고 생각하고 표를 적어보면 재밌는 법칙이 보입니다.

n번째 까지

x와 y값이 같은 원소를 기준으로 사선을 그었을 때 1행에선 1이 1번, 2행에선 2가 2번, 3행에선 3이 3번 나옵니다.

따라서 n행에선 n이 n번 나오는 것을 알 수 있습니다.

n=3, n=4일경우

이를 예제를 통해서 보면 더 쉽게 이해할 수 있습니다.

결과

따라서 배열의 인덱스를 n으로 나눈 나머지가 행(count)보다 작을 경우 행(count)를 넣고 그 외일경우 나머지+1을 넣어주면 됩니다. (+1을 하는 이유는 배열의 인덱스는 0부터 시작하기 때문)

이를 코드로 짜면 다음과 같이 나옵니다.

fun solution(n: Int, left: Long, right: Long): MutableList<Int> {
    val answer = ArrayList<Int>()
    var count = 1
    for (i in 0 until n*n) {
        if(i%n == 0 && i != 0)
            count++
        if(i%n < count)
            answer.add(count)
        else
            answer.add(i%n+1)
    }
    return answer.subList(left.toInt(), right.plus(1).toInt())
}

첫 번째 if문에서 0을 제외한 이유는 어떤 수로 0을 나눠도 나머지가 0이라 제외했습니다.

결과를 보게되면 런타임 에러와 메모리 초과가 엄청 많습니다. 단순히 주어진 n의 제곱만큼 반복하는 건데 메모리 초과가 뜬다는 것은 반복을 n^2만큼 하면 안된다는 의미입니다. 런타임 에러는 Long 타입 관련된 문제입니다.

범위를 left에서 right까지 잡고 행은 배열이 n개씩 끊어지므로 배열의 인덱스 / n + 1을 하면 구할 수 있습니다.

fun solution(n: Int, left: Long, right: Long): ArrayList<Int> {
    val answer = ArrayList<Int>()
    var count = left/n+1
    for (i in left ..right) {
        if(i%n == 0L && i != 0L)
            count++
        if(i%n < count)
            answer.add(count.toInt())
        else
            answer.add((i%n+1).toInt())
    }
    return answer
}

 

다른 사람의 풀이

import kotlin.math.max

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        return (left..right).map { (max(it / n, it % n) + 1).toInt() }.toIntArray()
    }
}

 

인덱스를 n으로 나눈 값과 나머지중 최대값에 1을 더해서 배열에 추가한 뒤 리턴해주고 있습니다.

왜 나눈 값과 나머지일까요?

 

n=3일 때를 나열해보면 다음과 같습니다. 초록색이 인덱스, 검은색이 만들어진 배열의 값, 빨간색이 이차원배열의 좌표입니다. 여기서 x값을 보면 인덱스를 n으로 나눈 나머지값임을 알 수 있고, y값은 나눈 결과값임을 알 수 있습니다. 따라서 각 좌표값은 (인덱스를 n으로 나눈나머지, 인덱스를 n으로 나눈 값) 으로 구할 수 있습니다.