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

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

첫 풀이

def solution(n, left, right):
    graph = [ [n for _ in range(n)] for _ in range(n) ]

    for i in range(n):
        graph[i][i] = i+1
        for j in range(i):
            graph[i][j] = i+1
            graph[j][i] = i+1

    arr = []

    for i in graph:
        arr += i

    answer = arr[left:right+1]

    return answer

시간 초과가 발생했다.

1 ≤ n ≤ 10^7 이라 이차원 배열은 절대 사용할 수 없는 것 같다.

두번째 풀이

def solution(n, left, right):
    graph = []
    elem = [ i for i in range(1,n+1)]

    for i in range(n):
        elem[:i+1] = [i+1]*(i+1)
        graph += elem

    answer = graph[left:right+1]
    print(answer)

    return answer

나름 줄였다고 생각했는데 여전히 시간초과가 발생했다.

아무래도 left 와 right 의 사이의 범위가 10^5 이므로 이 구간만 반복해야 시간초과가 발생하지 않을 것 같았다.

최종 풀이

def solution(n, left, right):
    # n = 4
    answer = []

    for i in range(left,right+1):
        x = i//n
        y = i%n
        val = max(x,y)+1
        answer.append(val)

    return answer

최종 풀이는 이차원 배열의 인덱스를 활용하되, 이차원 배열을 직접적으로 만들지 않는 방법을 사용했다.

각 칸의 값은 x,y 인덱스값에서 큰 값+1이라는 것을 활용하여 정답을 구할 수 있었다.