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

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

✍️ 첫번째 접근

입력으로 주어진 n에서부터 1까지 배열에 값을 채운다.
아래 그림에서 예시를 들면,

• i=3) 모든 배열 요소에 3을 채운다.
• i=2) 가장 바깥을 제외한 모든 배열 요소에 2를 채운다.
• i=1) 1행 1열에 1을 채운다.
  하지만 이렇게 값을 채울 경우 이미 접근했던 배열 요소에 다시 접근하므로 비효율적이므로 시간 초과가 발생하였다.

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var arr: [[Int]] = Array(repeating: Array(repeating: 0, count: n), count: n)
    for i in (1...n).reversed() {
        for j in 0..<i {
            for k in 0..<i {
                arr[j][k] = i
            }
        }
    }
    let joinedArr = Array(arr.joined()).map { Int($0) }
    return Array(joinedArr[Int(left)...Int(right)])
}

✍️ 두번째 접근

결국에 우리가 만들어야할 배열은 아래와 같다. 따라서, 첫번째 접근과 같이 2차원 배열을 만든 후 아래와 같은 1차원 배열로 변환하지 말고 바로 1차원 배열을 만들도록 구현하였다.

2차원 배열로 만든 후 1차원 배열로 변환하지 않고 바로 1차원 배열로 만들기 위해 아래와 같은 규칙을 발견할 수 있었다.
n이 3이라고 예를 들면,

• 1~3까지의 값을 배열에 넣는다.
• 1 다음 숫자인 2를 2개만큼 배열에 넣고 나머지 숫자인 3을 넣는다.
• n인 3을 3개만큼 배열에 넣는다.

또한, 배열에 값을 넣는데 크기가 right를 넘어갈 경우 굳이 넣을 필요가 없으므로 따로 예외 처리를 해주었다.

그럼에도 불구하고 시간 초과가 발생하였다.

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var answer: [Int] = []
    if n == 1 {
        return [1]
    }
    for i in 1...n {
        if answer.count > Int(right) {  // right를 넘어가면 굳이 할 필요가 없기 떄문
            break
        }
        var arr: [Int] = []
        if i == 1 {
            arr = Array(1...n)
            for j in arr {
                answer.append(j)
            }
        }
        else if i == n {
            if n + answer.count >= n*n {
                arr = Array(repeating: n, count: n*n-answer.count)
            }
            else {
                arr = Array(repeating: n, count: n)                
            }
            for j in arr {
                answer.append(j)
            }
        }
        else {
            if i + answer.count >= n*n {
                arr = Array(repeating: n, count: n*n-answer.count)
            }
            else {
                arr = Array(repeating: i, count: i)                
            }
            for j in arr {
                answer.append(j)
            }
            var remainder: [Int] = []
            if i + answer.count >= n*n {
                remainder = Array(i+1...n*n-answer.count)
            }
            else {
                remainder = Array(i+1...n)   
            }
            for j in remainder {
                answer.append(j)
            }
        }
    }
    return Array(answer[Int(left)...Int(right)])
}

✍️ 세번째 접근

left 이전의 값과 right 이후의 값을 굳이 계산할 필요가 없으므로 해당 범위에 대해서만 계산한다. 약간의 힌트를 얻어, 배열로 만들어지는 원소들의 인덱스를 적어 규칙을 찾아내어 해결하였다.
느낀 점은 매번 느끼는거지만 문제에서 주어지는 범위가 매우 크다면 문제를 바라보는 시각을 달리 봐야한다는 것이다.

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var answer: [Int] = []
    for i in Int(left)...Int(right) {
        answer.append(max(i/n, i%n) + 1)    // 각 원소의 행과 열을 구해 그 값들의 최대값을 구하고 원소의 값은 그 최대값보다 1 크므로 +1을 한다.
    }
    return answer
}