n^2 배열 자르기 Swift

문제 설명

정수 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 ≤ 10^7
• 0 ≤ left ≤ right < n^2
• right - left < 10^5

---

내가 푼 풀이

처음에는 그냥 2차원 배열을 구해서 1차원배열로 만들고 그에 해당하는 인덱스의 범위를 출력하려고 했는데

주어지는 n의 최대크기가 10^7 이라서, 2중 for문을 이용하면 무조건 시간초과가 뜨겠다 싶어서 해당하는 인덱스의 범위만 구하고

해당 배열이 만들어지는 규칙을 적용해서 정답을 출력하기로 했다.

이 문제에 적용한 배열이 만들어지는 규칙은 i행 1열부터 i열까지의 원소는 전부 i, i행 i+1열부터는 i+1, i+2 ... 이다.

ex) n = 3 일때 3x3 행렬 3행 1열 부터 3열까지는 전부 3이다.

ex) n = 5 일때 5x5 행렬 3행 1열 부터 3열까지는 전부 3이다. 3행 4열은 3+1 = 4, 3행 5열은 3+2 = 5 이다.

 

구하고자하는 범위 [left...right] 의 배열

전부 n으로 나눈 나머지 그 행의 순서가 나온다. 

전부 n으로 나눈 몫으로 바꾸면 그 행의 번호가 나온다. 

해당하는 위치의 순서가 행의 번호 보다 작거나 같으면 그 위치의 원소는 행의번호

해당하는 위치의 순서가 행의 번호 보다 크다면 그 위치의 원소는 행의번호 + (행의순서 - 행의번호 )

배열의 원소는 인덱스로 구성되어있으니 출력할때 +1을 해준다.

글로만 봐서는 헷갈리니까 예제문제로 예시를 들어본다.

 

ex) n = 3 , 3x3 행렬, left = 2, right = 5 

[[1,2,3],

 [2,2,3],

 [3,3,3]]

• 구하고자 하는 범위의 인덱스를 배열로 만든다. :  [2,3,4,5]
• 인덱스 배열을 3로 나눈 나머지 :  [2, 0, 1, 2] ( 행의 순서)
• 인덱스 배열을 2으로 나눈 몫 : [0, 1, 1, 1] (행의 번호)

인덱스배열 첫번째 2

행의 번호: 0 ,행의 순서: 2

행의 순서가 행의번호보다 크다. 결과는 행의번호 + 행의순서 - 행의번호 = 2 

위에 숫자는 전부 배열의 인덱스 이므로 +1 해서 출력한다 -> 3

 

인덱스배열 두번째 3

행의번호: 1, 행의순서: 0

행의번호가 더 크다. 결과는 행의번호

숫자는 배열의 인덱스이므로 +1을 해서 출력한다 -> 2

 

인덱스배열 세번째 4

행의번호: 1, 행의순서: 1

행의번호와 행의순서가 같다. 결과는 행의번호

숫자는 배열의 인덱스이므로 +1을 해서 출력한다 -> 2

 

인덱스배열 세번째 5

행의번호: 1, 행의순서: 2

행의순서가 행의번호 보다 크다. 결과는 행의번호 + 행의순서 - 행의번호 = 2

숫자는 배열의 인덱스이므로 +1을 해서 출력한다 -> 3

 

이런 규칙을 적용하여 풀었다.

 

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var arr = Array(left...right)
    var rows: [Int64] = arr.map{ $0 % Int64(n)}
    var cols: [Int64] = arr.map{ $0 / Int64(n)}
    var result = [Int]()
    
    for i in 0..<rows.count {
        var num = cols[i] + 1
        if rows[i] <= cols[i] {
            result.append(Int(num))
        }  else {
            result.append(Int(num + (rows[i] - cols[i])))
        }
    }
    return result
}