[프로그래머스] Swift - n^2 배열 자르기 (LV.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 < n^2
• right - left < 10^5

 

입출력 예제

n	left	right	result
3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

1번 예제

2번 예제

풀이 [ 메모리: 35mb, 최대시간:  4.02ms ] 

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

        result.append(y > x ? y : x)
    }
    
    return result
}

문제를 받고 생각한 것.

1. n의 범위가 10^7로, 시간복잡도를 신경써야하는 문제.
2. 전체 범위를 탐색하면 시간 초과에 걸릴 수 있다.
3. 2차원 배열을 좌표로 변환하여 그려보면, (y, x)좌표 중 큰 값이 2차원 배열에 들어있는 규칙을 찾을 수 있다.
4. x좌표는 0, 1, 2, 3, ... 의 반복이며, y좌표는 x좌표가 끝이 나야 y+1이 되는 것을 알 수 있다.
5. 하지만 앞서 말했듯 전체 범위를 탐색하면 안 되고, left~right의 범위(10^5)만 탐색해야 한다.
6. 앞의 값이 무엇인지 확인할 필요 없이, x와 y값을 대입할 수 있어야 한다.
7. 2차원 배열의 (y, x)좌표를 1차원으로 이어붙이면, (y,x)좌표는 0, 1, 2, 3, 4, 5, 6, ... 등의 인덱스를 가지며, 이 값의 몫과 나머지를 이용해 2차원 배열의 (y, x) 좌표를 알 수 있다.

 

<규칙 설명 - 예제 1>

1	2	3
2	2	3
3	3	3

(1, 1)	(1, 2)	(1, 3)
(2, 1)	(2 ,2)	(2, 3)
(3, 1)	(3, 2)	(3, 3)

2차원 배열과 좌표

 

값	1	2	3	2	2	3	3	3	3
좌표	(1, 1)	(1, 2)	(1, 3)	(2, 1)	(2 ,2)	(2, 3)	(3, 1)	(3, 2)	(3, 3)
1차원 index	1	2	3	4	5	6	7	8	9

2차원 배열을 1차원으로 이어붙였을 때, 각 index

해당 인덱스를 n값으로 나눈 몫, 나머지가 (y, x)이다.