[Lv. 2] N^2 배열 자르기

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

난이도 : Level.2

언어 : Kotlin

 

문제 설명 :

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

• n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
• i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
  • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
• 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
• 새로운 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

입출력 예 :

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

풀이 : 

fun solution(n: Int, left: Long, right: Long): IntArray {
        val arr = Array(n) { i -> IntArray(n) { j -> if (i + 1 >= j + 1) i + 1 else j + 1 } }

        return arr.joinToString("") { it.joinToString("") }.slice(left.toInt() .. right.toInt()).chunked(1).map { it.toInt() }.toIntArray()
    }

 

처음은 위와 같이 접근 했으나, 제출 후 실패와 동시에 메모리 초과를 보게 되었다.

제한사항과 left, right를 보고 다시 생각해야겠다고 느꼈다.

 

fun solution(n: Int, left: Long, right: Long): IntArray {
        val arr = IntArray((right - left).toInt() + 1)
        var index = left

        repeat(arr.size) {
            val x = (index / n.toLong()).toInt()
            val y = (index % n.toLong()).toInt()

            arr[it] = x.coerceAtLeast(y) + 1
            index++
        }

        return arr
    }

 

규칙 자체는 동일하다

(x, y) 꼴이라고 쳤을 때, index가 증가하면 x, y 중 큰 값에 +1을 시켜주는 것.

 

(0, 0)	(0, 1)	(0, 2)
(1, 0)	(1, 1)	(1, 2)
(2, 0)	(2, 1)	(2, 2)

1	2	3
2	2	3
3	3	3

이를 펼치면

1, 2, 3, 2, 2, 3, 3, 3, 3 이 나오게 되고, 여기서 left .. right를 출력하는 것이다.

[3, 2, 2, 3]

 

2차원 배열을 1차원 배열 인덱스로 변환하여 푸는 것

index를 6, n을 4라고 치면,

x = 6 / 4 = 1

y = 6 % 4 = 2

x = 1, y = 2 이므로 큰값 y에 +1을 하여 3이 나온다.

 

다음과 같은 방식을 반복.