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

문제

n^2 배열 자르기

풀이 과정

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        var answer: IntArray = intArrayOf()
        
        //2차원 리스트 생성 및 i 값으로 초기화
        var initialList = MutableList<MutableList<Long>>(n) { i -> MutableList<Long>(n) { j -> if (i >= j) (i+1).toLong() else (j+1).toLong() } }
        
        //배열 이어 붙이기
        var oneLineList: MutableList<Long> = mutableListOf()
        initialList.forEach { i ->
            i.forEach { j ->
                oneLineList.add(j)
            }
        }

        //범위 값 뽑아내기
        for (i in 0 until oneLineList.size) {
            if (i >= left && i <= right) {
                answer += oneLineList[i].toInt()
                
                if (i.toLong() == right) {
                    break
                }
            }   
        }
        
        return answer
    }
}

처음에는 문제에서 주어지는 흐름대로 코드를 작성했다.

처음 2차원 리스트를 생성할 때 내부 리스트 초기화를 n번 해야하고, 조건문에 따라 비교 연산도 해야한다.

배열 이어 붙이기 파트에서는 위에서 초기화하면서 값이 추가된 initialList를 모두 순회하면서 oneLineList에 값을 추가해야한다.

범위 값 뽑아내기 파트에서는 onLineList에 첫 번째 요소부터 접근해야하는데, left와 right 범위에 있는지 검사 후 answer에 값을 더하게 된다. 인덱스가 right번째라면 검사를하여 반복문을 중단시키지만, 만약 right가 oneLineList의 마지막 인덱스 값 만큼 주어진다면 결국 모든 요소를 돌게 되는 것이다.

이렇게 위의 3개 파트를 실행해야하므로 n이 커질 수록, right 수가 클 수록 처리가 늘어나게 된다.

역시나 제출을 하니 시간 초과와 메모리 초과가 발생하였다. 메모리 초과가 많은 걸 보니 n의 크기가 상당한 것들로 검사를 하는 것 같다.

1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다. 부분을 보면 분명 한 줄짜리로 리스트를 만들 때 패턴을 잡을 수 있을 것 같았다.

특히 이런 문제는 /과 %를 이용하여 쉽게(?) 풀어버리는 사례를 몇번 봤었던 것 같았고 이리저리 짱구를 굴려보다가 아래와 같은 패턴을 발견했다.

한줄짜리 리스트의 인덱스에 따라 값을 추론을 수 있다면, 단순히 left ~ right 사이의 값만 취할 수 있게 된다.

최종 코드

class Solution {
    fun solution(n: Int, left: Long, right: Long): IntArray {
        var answer: IntArray = intArrayOf()        
        for (i in left .. right) {
            var divide = i / n
            var mod = i % n
            if (divide >= mod) {
                answer += (divide + 1).toInt()
            }
            else {
                answer += (mod + 1).toInt()
            }
        }        
        return answer
    }
}

---

[TIL-240411]