Algorithm / n^2 배열 자르기

문제

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

1) 문제 풀이

func solution(_ n:Int, _ left: Int64, _ right: Int64) -> [Int] {
    var answer: [Int] = []
    
    for i in 1...n {
        var arr: [Int] = []
        arr.append(contentsOf: i...n)
        
        if arr.count < n {
            let count = n - arr.count
            arr = Array(repeating: i, count: count) + arr
        }
        
        answer = answer + arr
    }
        
    return Array(answer[Int(left)...Int(right)])
}

결과

2) 코드 개선

⚠️ 문제점 요약

• n의 범위는 최대 10^7, 즉 1억 원소(10^7 * 10^7)는 만들 수도 없고, 저장할 수도 없음
• 현재 코드는 n*n 배열을 전부 만들어서 붙이려고 시도
• answer = answer + arr처럼 매 루프마다 +로 배열을 누적하면 시간 복잡도는 O(n^2)

✅ 개선 포인트

• 규칙을 찾아서 직접 계산
  • 2차원 배열의 (i, j)의 위치값은 max(i + 1, j + 1)이라는 규칙이 있음
  • 즉, 전체 2차원 배열을 펼친 1차원 배열의 k번째 요소는 아래와 같음

  let row = k / n
   let col = k % n
   let value = max(row, col) + 1

• 해결 방법
  • left부터 right까지 인덱스에 대해서만 위 규칙으로 계산하면, 배열 전체를 만들 필요가 없음
  • 시간 복잡도는 O(right - left + 1) -> 제한 조건에 따라 최대 10^5로 통과 가능성 높음

func solution(_ n: Int, _ left: Int64, _ right: Int64) -> [Int] {
    var result: [Int] = []

    for k in left...right {
        let row = Int(k / Int64(n))
        let col = Int(k % Int64(n))
        result.append(max(row, col) + 1)
    }

    return result
}

결과