문제 설명

---

정수 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]만 남기고 나머지는 지웁니다.

제한사항

• 1 ≤ n ≤ 10⁷
• 0 ≤ left ≤ right < n²
• right - left < 10⁵

입출력 예

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

max 함수를 사용한 배열 채우기

---

문제에서 2차원 배열의 각 원소는 max(i, j) + 1 (여기서 i, j는 0부터 시작하는 인덱스)로 결정된다.

Index	0	1	2
0	1	2	3
1	2	2	3
2	3	3	3

표 설명

• (0, 0):
  • 행 0, 열 0 → max(0, 0) + 1 = 0 + 1 = 1
• (0, 1):
  • 행 0, 열 1 → max(0, 1) + 1 = 1 + 1 = 2
• (0, 2):
  • 행 0, 열 2 → max(0, 2) + 1 = 2 + 1 = 3

초기 접근 방식 (시간초과 발생)

---

처음 시도에서는 전체 n × n 배열을 먼저 구성한 후, 이를 flatten하여 슬라이싱하는 방법을 사용했다.
하지만 n의 크기가 매우 클 경우 모든 원소를 생성하고 1차원 배열로 변환하는 과정에서 시간과 메모리 사용이 급증하여 시간초과 문제가 발생했다.

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var numbers: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: n)
    
    for i in 0..<n {
        for j in 0..<n {
            numbers[i][j] = max(i + 1, j + 1)
        }
    }

    return Array(numbers.flatMap { $0 }[Int(left)...Int(right)])
}

최적화된 접근 방식

---

시간초과 문제를 해결하기 위해 전체 배열을 생성하지 않고, 인덱스 계산만으로 필요한 값만 구하는 방법을 사용했다.
1차원 배열에서 각 인덱스 i에 대해, 다음과 같이 계산할 수 있다:

• row = i / n
• col = i % n
• 해당 위치의 값은 max(row, col) + 1

즉, left부터 right까지 각 인덱스에 대해 위 계산을 수행하면 전체 배열을 생성할 필요 없이 원하는 값을 얻을 수 있다.

import Foundation

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