코딩테스트 연습 - n^2 배열 자르기

문제 풀이 아이디어

함정…

여러 개의 코테 문제를 풀어봤지만 문제에서 애니메이션까지 보여주면서 친절하게 설명하는 경우는 처음 봤습니다. 애니메이션에 나온대로 2차원 배열을 구현하고 각 행을 이어붙여서 1차원 배열을 만들고 subscript를 활용해서 left ~ right까지 잘라서 리턴하면 해결입니다.

하지만 이렇게 풀면 100% 시간초과입니다. 일단 n이 최대 10^7입니다. 그런데 위에서 말한대로 2차원 배열을 만들면 무조건 이중반복문을 사용해야 하는데 그렇다면 연산횟수가 최대 10^14가 됩니다. 무조건 O(N)의 시간복잡도를 가진 코드를 사용해야 합니다.

규칙을 찾자!

이중반복문을 통해서 직접 구하는 방법이 안된다면 규칙을 찾아야 합니다.

이차원 배열의 i행 j열의 값은?

일단 이차원 배열의 i행 j열에 위치한 숫자를 구하는 규칙을 찾아봅니다. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자를 i로 채우는 규칙과 애니메이션에 제시된 이차원 배열을 보면 i행 j열에 위치한 숫자는 i와 j 중에서 큰 값에 1을 더한 값임을 알 수 있습니다.

일차원 배열의 index는 이차원 몇행몇열일까?

이제 이차원 배열을 일차원 배열로 바꿨을 때 일차원 배열의 index가 이차원 배열의 몇행몇열이었는지 알 수 있다면 문제를 해결할 수 있습니다. 아주 간단합니다. 길이가 n인 행을 이어붙인 것이므로 index를 n으로 나눈 몫이 행, 나머지가 열이 됩니다.

코드

위의 규칙을 활용해서 만든 코드입니다. 코드 내부의 반복문은 1개로 N은 right - left입니다. 문제에서 주어진 right - left의 최댓값은 10^5이므로 충분히 시간 내에 통과할 수 있습니다.

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