n^2 배열 자르기

📍 n^2 배열 자르기

💡 문제

정수 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 * n 크기의 2차원 리스트를 만든다.
- 각 칸의 행 번호와 열 번호 중 더 큰 값이 곧 해당 칸의 값이 된다.
2차원 리스트를 평탄화 시켜 자르는 방법도 있겠지만, 나는 left가 위치한 행부터 right가 위치한 행까지 먼저 크게 잘라주었다.
- 왜냐하면 left와 right가 Long형이여서 바로 slice 함수에 넣어줄 수 없었다.
- 그 후, 잘라진 리스트를 평탄화 해 left 부터 left + (right - left)의 길이만큼 다시 잘라주었다.

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        val list = List(n) { col -> List(n) { row -> if (col > row) col+1 else row+1 } }
        
        val len = (right - left).toInt()
        val (startCol, startRow) = Pair((left / n).toInt(), (left % n).toInt())
        val (endCol, endRow) = Pair((right / n).toInt(), (right % n).toInt())
        
        val t = list.slice(startCol..endCol).flatten().slice(startRow..startRow+len)
    
        
        return t.toIntArray()
    }
}

제한사항을 무시한 나는 메모리 초과와 시간 초과라는 결과를 만나게 되었다.

메모리 초과: 리스트에 너무 많은 값을 저장했다. (n * n의 크기는 생각보다 컸다.)
시간 초과: 리스트를 초기화할 때 너무 많은 시간이 소요되고, 자르고 > 평탄화하고 > 다시 자르는 과정도 비효율적이다.

✌️ 두 번째 풀이 (성공)

각 칸의 값들은 **"행과 열 중 더 큰 값"**이다는게 중요하다.
- 구하려는 배열의 크기(right - left)는 생각보다 작다.
- 굳이 n * n의 배열을 다 초기화해 줄 필요가 없다.
애초에 left가 있는 행부터 right가 있는 행까지만의 배열을 만들었다.
- 이 때의 행 번호는 left / n 부터 시작한다.
- 즉, left / n 행부터 right / n 행까지의 배열을 만들면 된다.
배열을 잘라줄 때는 첫 번째 풀이에서 한 것처럼 시작 인덱스부터 시작 인덱스에 구하고자 하는 길이를 더한 인덱스까지 자르는 방식을 사용했다.

 
class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        val len = (right - left).toInt()
        val cols = (right/n - left/n).toInt()
        val realStart = (left % n).toInt()
 
        val list = List(cols+1) { col -> List(n) { row -> if (left/n+col > row) (left/n+col+1).toInt() else row+1 } }
 
        return list.flatten().slice(realStart..realStart+len).toIntArray()
    }
}

최대값을 구할 때 조건문 말고 max()를 사용하는 방법이 있겠지만, 일단 그냥 풀어보았다. 문제 풀이에는 성공했지만 마음에 드는 풀이는 아니었다. 배열을 초기화하는데 사용되는 변수들이 너무 많고, 정수형 배열로 변환해주어야 하는 것도 마음에 안들었다.

🔥 다른 사람의 풀이

내가 너무 어렵게 생각했던 걸까? 다른 사람들의 풀이를 보니 생각보다 간단히 풀리는 문제였다. 내가 미처 생각하지 못했던 건, i번째 칸의 값을 배열의 초기화 없이 구할 수 있다는 것이다.

i번째 칸의 행 번호는 i / n + 1이다.
- 문제에서의 배열은 0이 아닌 1부터 시작하기 때문에 1을 더해줘야 한다.
i번째 칸의 열 번호는 i % n + 1이다.
이걸 이용해 left부터 right까지의 값을 구할 수 있다.

문제에서 2차원 배열을 만들고.. 1차원으로 만들고.. left부터 right까지 자르고.. 하는 과정으로 설명했다보니까 너무 거기에 갇혀있었던 것 같다.

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

💭 후기

정말 간단한 문제였는데.. 너무 돌아돌아 푼 것 같다. 심지어 두 번째 풀이에서 left와 right를 이용해 행과 열의 번호도 구했으면서!! 왜 눈치채지 못했을까!! 너무 아쉽다. 그렇지만 이 문제 덕분에 2차원 배열을 초기화하는 걸 연습할 수 있어서 좋았다. 언젠가 쓰일 날이 오겠지.