코딩테스트 - [Swift] n^2배열 자르기

n^2 배열 자르기

문제 설명

정수 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 < n2
• right - left < 105

---

 

입출력 예

n     left      right   result

3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

 

---

입출력 예 설명

입출력 예 #1

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

입출력 예 #2

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

풀이

제약 조건) n이 10^7까지 나왔을 경우 2차원 배열을 생성해서 슬라이싱하고 인덱스에 맞게 자르기에는 시간이 부족하므로 규칙을 찾아야 한다.

N = 4

1 2 3 4                                    index)   0   1   2   3   4   5   6   7   8   9  10 11  12  13  14  15

2 2 3 4      를 슬라이싱 할경우        값)  0   1   2   3   4   2   2   3   4   3   3   3   4   4    4   4   

3 3 3 4

4 4 4 4

 

규칙을 찾아야 한다.

n = 4

index = 0                      1                             2                  3                   4                    8                      12

       (0, 0) = 1,          (0, 1) = 2,              (0, 2) = 3     (0, 3) = 4    (1, 0) = 2       (2, 0) = 3           (3, 0) = 4..

 

규칙 1. 

규칙을 보면 4가 되기 전까지 의 행 값은 모두 0이다. 8일땐 2가되며 12일땐 3이 된다

 행 =  index / n

 

규칙 2.

열의 값은 0, 1, 2, 3, 0 으로 순환한다. n의 값이 4이니까  0, 1, 2, 3만 등장한다는건 index % 4라고 추리할 수 있다

열 = index % 4

 

규칙 3.

(0, 0) = 1,          (0, 1) = 2,              (0, 2) = 3     (0, 3) = 4    (1, 0) = 2       (2, 0) = 3           (3, 0) = 4..

를 보면 행, 열 중 큰 숫자에 + 1이 되는걸 알 수 있다

그렇다면 max(x, y) + 1

 

규칙1.로 행을 구하고,

규칙2.를 활용해 열을 구하고,

구한 열과 행을 규칙 3을통해 index의 값을 구한다.

 

코드

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var result = [Int]()
    
    for i in left...right{
        result.append(max(Int(i) / n, Int(i) % n) + 1)
    }
    
    return result
}

/*규칙
  0123

0 1234
1 2234
2 3334
3 4444

x, y = 값
0, 0 = 1
0, 1 = 2
0, 2 = 3
1, 0 = 2
2, 1 = 3
3, 1 = 4

규칙 1. 값 = 행, 열의 인덱스중 큰 것에 + 1
 ------------------------------
 1차원 배열로 만든
 1234223433344444
각 숫자의 행, 열 값
행 = 0000111122223333
열 = 0123012301230123

idx   =  0    1    2    3     4     5    6
point = 0,0  0,1  0,2  0,3   1,0   1,1  1,2

규칙 2.
행 = index / n
열 = index % n
 */

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var result = [Int]()
    
    for idx in left...right{
        let row = Int(idx) / n
        let col = Int(idx) % n
        
        result.append(row > col ? row + 1 : col + 1)
    }
    return result
}