프로그래머스 - n^2 배열 자르기

프로그래머스 - n^2 배열 자르기

 

 

 문제 설명

 

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

 나의 풀이

 

시간초과가 날거라고 생각했지만 문제가 말하는대로 구현을 해보고 싶어서 한 풀이이다.

 

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    
    var arr3 = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)
    var result: [[Int]] = [[]]
    arr3[0][0] = 1
    
    for i in 1..<n {
        for j in 0..<i {
            arr3[i][j] = i+1
            arr3[j][i] = i+1
        }
        arr3[i][i] = i+1
    }
    
    arr3.forEach { arr in
        result.append(arr)
    }
    
    let mapArr = result.flatMap {$0}
    return Array(mapArr[Int(left)...Int(right)])
}

 

이 풀이 이후에 특정 인덱스일때 특별한 규칙이 있는 걸 알았다.

예시로 n이 4일때

0행 -> 1234

1행  -> 2234

2행  -> 3334

3행  -> 4444

 

그래서 left와 right의 행을 구하고 그 사이에 있는 범위만큼의 배열을 위의 규칙을 이용해서 1차원 배열에 넣었다.

만들어진 1차원 배열은 left에 해당하는 인덱스 행의 첫번째 원소부터 있기 때문에 그 전까지의 값인 행의 수 * n만큼을 빼주어 일치시켰다.

 

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var arr: [Int] = []
    var left = Int(left)
    var right = Int(right)
    
    let startRow = left / n
    let endRow = right / n
    
    for i in startRow...endRow {
        for _ in 0...i {
            arr.append(i+1)
        }
        for k in i+1..<n {
            arr.append(k+1)
        }
    }
    let startIdx = left - (startRow * n)
    let endIdx = right - (startRow * n)
    return Array(arr[startIdx...endIdx])
    
}

 

위 풀이가 동작할 수 있는 이유는 left와 right의 차이가 10^5이하이기 때문이다. 

 

 

 다른 사람의 풀이

 

arr[0][0] = 1이고, arr[1][0], arr[0][1], arr[1][1] = 2인 것을 보고 i와 j중 더 큰 것 + 1이 배열의 값인 것을 이용한 풀이이다.

 

배열의 행은 i / n, 열은 i % n인 것을 알면 바로 생각했을 것 같은데 나는 바로 생각하지 못했다.

이 구조를 숙지하고 가면 좋을 것 같다.

 

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var left = Int(left)
    var right = Int(right)
    
    return Array(left...right).map{
        return max($0 / n + 1, $0 % n + 1)
    }
}