[Swift 알고리즘] Programmers n^2 배열 자르기

○

Level 2 월간 코드 챌린지 시즌3 (1시간)

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 < n^2
- right - left < 10^5

입출력 예시

print(solution(3,2,5)) //[3,2,2,3]
print(solution(4,7,14)) //[4,3,3,3,4,4,4,4]

내 답안 

import Foundation

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

n행 n열의 2차원 배열의 행열에서 규칙을 찾아보면, 

n이 3일 때, n의 행 값(1 1 1 2 2 2 3 3 3)은 index를 n으로 나누었을 때의 몫 + 1 (= i/n + 1) 의 값을 가지고

n의 열 값(1 2 3 1 2 3 1 2 3)은 index를 n으로 나누었을 때의 나머지 + 1 (= i%n + 1) 의 값을 가지는 것을 알 수 있다. 

이 규칙을 적용하여 left ... right 범위 내에서 for문을 한 번만 돌리면, 시간초과 없이 문제를 통과할 수 있다.

 

1차 시도 : 30점 시간초과

단순하게 그냥 이중 for문 돌려서 차례대로 값을 구하도록 구현해보았다.

그럴 줄 알았지만 역시나 시간초과. n의 최대 범위가 천만이므로, 범위 n으로 이중 for문을 돌리면 음.. 100조..? 숫자 세는 것도 힘드네

암튼 당연하게 시간초과가 뜬다. 

-> 규칙을 찾아서 left ~ right 까지 한번만 반복문을 돌리는 것이 포인트⭐️!!

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