문제

정수 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$

틀린 풀이

진짜 문제에서 시키는 대로 한 풀이. n의 범위를, 그리고 left, right의 범위를 보면 절대 문제에서 시키는 대로 하면 안 된다는 것을 알 수 있다. 공간도 엄청 많이 쓰고 시간초과도 나기 때문.

• 코드 보면 시간복잡도가 $O(N^2)$인데 최댓값인 $10^7$을 넣으면 $10^{14}$... 딱 봐도 안 되겠쥬
• 그러면 우리는 최대 $O(N)$안에 끝내야 한다는 인사이트를 얻을 수 있음

def solution(n, left, right):
    board = [[0] * n for _ in range(n)]
    for i in range(n):
        for col in range(n):
            board[i][col] = i+1
        for row in range(n):
            board[row][i] = i+1
    arr = []
    for i in range(n):
        arr = arr + board[i]
    
    return arr[left:right+1]

올바른 풀이

만약에 n이 4라고 할 때, 2차원 배열을 각각의 행으로 끊어본다면 다음과 같이 된다.

• [1, 2, 3, 4]
• [2, 2, 3, 4]
• [3, 3, 3, 4]
• [4, 4, 4, 4]

즉, k(k >= 1)번째 행에서는 k가 k번 나오고, 나머지 (n-k)번 만큼은 k에서 하나씩 증가하는 수로 채워진다.

이러한 규칙을 이용해서, 어떤 인덱스를 넘겼을 때, 그게 몇 번째 행인지 알아내서 [3, 3, 3, 4]와 같은 행 한 줄을 뱉어내는 함수(makeRow)를 만든다. 이게 핵심아이디어이다.

start, end가 주어졌을 때, n으로 나눈 몫을 행번호로 구한 다음

• 구한 행번호 두 개가 모두 같은 경우
• 다른 경우

를 나눠서 생각한 다음, 각 행마다 반복문을 돌려서 다음과 같은 로직을 수행한다.

• 현재 행번호가 시작행번호라면, makeRow로 만들어낸 행에다가 인덱스 슬라이싱을 이용해서 필요한 부분만큼만 잘라낸다.
• 현재 행번호가 시작행번호와 끝행번호 사이라면 그냥 makeRow로 만들어낸 행 통째로 이어붙여준다.
• 현재 행번호가 끝행번호라면 makeRow로 얻어낸 행에다가 인덱스 슬라이싱을 이용해서 필요한 부분만큼(앞부분)을 잘라내서 붙여준다.

코드

def solution(n, left, right):
    arr = []
    def makeRow(no):
        ret = [(no+1)] * (no+1)
        for i in range(n - no - 1):
            ret.append(no+1+i+1)
        return ret
    
    start = left // n
    end = right // n
    
    if start == end:
        temp = makeRow(start)
        return temp[left%n:right%n+1]
    
    for index in range(start, end+1):
        if index == start:
            arr += makeRow(start)[left%n:]
        elif index == end:
            arr += makeRow(end)[:right%n+1]
        else:
            arr += makeRow(index)
    
    return arr

다른 사람 풀이

그것보다 더 대박인 것은...
어떤 인덱스(i)가 주어졌을 때, 우리가 구하는 수는 max(i//n, i%n)+1 이라는 것이었다.

def solution(n, left, right):
    answer = []
    for i in range(left,right+1):
        answer.append(max(i//n,i%n)+1)
    return answer