[프로그래머스] Lv 2. n^2 배열 자르기(Kotlin)

코딩테스트 연습 - n^2 배열 자르기

 

문제

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

 

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1,2,3,...,n에 대해서, 다음 과정을 반복합니다.
   1. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[lef+1],...,arr[right]만 남기고 나머지는 지웁니다.

 

주어진 과정대로 만들어진 1차원 배열을 return하도록 solution 함수를 완성해주세요.

 

제한사항

1 <= n <= 10^7
0 <= left <= right < n^2 (최대 10^14)
right - left < 10^5

 

풀이

문제를 보고 가장 먼저 생각한 것은 1부터 n까지 모든 숫자에 대해서 위의 과정을 반복하고,

left ~ right까지의 원소를 구하는 방법이 최선일까 생각해본 것이었습니다.🤔

 

특정 행과 열을 알았을 때, 해당 위치의 원소를 바로 알아내는 방법은 없을까...

 

먼저 left~right까지의 숫자가 주어질 때, 행과 열을 알아내는 방법은 간단합니다.

val row = num / n // 행
val column = num % n // 열

 

그럼 행과 열을 알았으니, 해당 위치의 값을 알아내도록 하겠습니다.

예제에서도 보여주고 있지만, 문제에서 제시하는 과정을 반복하면 아래와 같은 규칙이 보이는 것을 알 수 있습니다.

 

y(열)이 x(행)보다 작거나 같을 때는 x(행) + 1과 같고,

y(열)이 x(행)보다 클 경우에는 y(열) + 1과 같습니다.

 

이를 코드로 나타내면, 아래와 같습니다.🤗

if (y<=x) x+1 else y+1

이렇게 수학적으로 풀면, 모든 테케를 통과하실 수 있습니다.👍

 

코드

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