[프로그래머스][파이썬] LV.2 n^2 배열 자르기

문제

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

풀이

내 풀이

1차

def solution(n, left, right):
    answer = []
    # n행 n열 크기의 비어있는 2차원 배열 생성
    a = [[0]*n for i in range(n)]
    
    # 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
    for i in range(0, n):
        for j in range(0, n):
            a[i][j] = max(i, j) + 1
            
    # 새로운 1차원 배열을 arr이라 할 때, 
    arr = sum(a, [])
    
    #arr[left], arr[left+1], ..., arr[right]만 남김
    answer = arr[left:right+1]
    
    return answer

시간초과 나와서 실패한 코드. 문제의 조건에서 1 ≤ n ≤ 10^7라고 했기에 배열을 전부 생성하는 방식으로 가면 안될 것 같음.

2차

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

• left / n, left % n의 값을 이용하면 전부 구하지 않아도 될 것 같다고 판단.
• i // n +1의 값은 행의 값, i%n+1의 값은 열의 값
• 행과 열 값 중 큰 것이 들어가게되는 값이 된다.