[10/18] n^2 배열 자르기

레벨2 문제

내 코드 (시간초과)

def solution(n, left, right):
    arr = [[0] * n for _ in range(n)]
    train = []
    
    for i in range(n):
        for j in range(n):
            target = max(i, j) + 1
            arr[i][j] = target
        train += arr[i]
    
    answer = train[left:right+1]
    return answer

BFS (시간초과)

from collections import deque

def solution(n, left, right):
    if (n == 1):  # n이 1일 경우
        return [1]
    
    arr = [[0] * n for _ in range(n)]
    arr[0][0] = 1
    arr[0][1], arr[1][0], arr[1][1] = 2, 2, 2
    
    queue = deque()
    queue.append([0, 1])
    queue.append([1, 0])
    queue.append([1, 1])
    
    while queue:
        h, w = queue.popleft()
        
        if (h >= n-1 or w >= n-1):
            break
        
        if (h == 0):
            arr[h][w+1] = arr[h][w] + 1
            arr[h+1][w+1] = arr[h][w] + 1
            queue.append([h, w+1])
            queue.append([h+1, w+1])
        elif (w == 0):
            arr[h+1][w] = arr[h][w] + 1
            arr[h+1][w+1] = arr[h][w] + 1
            queue.append([h+1, w])
            queue.append([h+1, w+1])
        else:
            arr[h+1][w+1] = arr[h][w] + 1
            queue.append([h+1, w+1])
            
    train = []
    for i in range(n):
        train += arr[i]
    
    answer = train[left:right+1]
    return answer

로직

• 복잡한 수학적 공식이 필요...