Programmers. n^2 배열 자르기

문제 설명
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 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	result
3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

 

---

문제 접근

1.2차원 배열을 만들고 i행 i열까지 알맞은 숫자를 모두 채운다

2.2차원 배열을 1차원배열로 만든다

3.1차원배열을 슬라이스 해서 [left:right+1]만큼 쪼갠다

 

이 방법은 시간복잡도가 O(n^2)이 되는데 최악의 경우 n이 10^7이기에 전체배열을 생성하는것은 비효율적이다.

 

우리는 1차원 배열에서 [left:right+1] 값만 result 값으로 반환하면 되기 때문에 규칙성을 살펴보자.

n이 3일때, [1,2,3,2,2,3,3,3,3] 이고 left 2 right 5일때 result는 [3,2,2,3]이다.

2차원배열이 있다고 가정했을때 1차원 배열의 인덱스는 각각 (0,0)->(0,1)->(0,2)->(1,0)->(1,1)....->(n-1,n-1)이다.

즉 행은 0,0,0,1,1,1,2,2,2....로 증가하고  열은 0,1,2,0,1,2로 반복된다.

for i in range(left,right+1):

    row = i//n 

    col = i%n 

 

n*n배열의 규칙성을 살펴보자. (row,col)라고 했을때 row나 col의 최대값에 1을 더한 것이 해당 좌표의 값이다.

 

즉 정답은 [left:right+1] 범위 내에 실제 인덱스값을 토대로 값을 정해서 arr에 append한 뒤 반환하면 된다!

 

배운 점

• 크기가 n*n인 2차원 배열 생성

arr = [[1]*n for _ in range(n)]

 

• 시간 복잡도에 유의하고 index의 규칙성을 잘 발견하자!

---

코드

 

def solution(n, left, right): #인덱스의 성질을 잘 파악하자
    arr =[] #left와 right 성질을 잘 파악해서 append
    for i in range(left,right+1):
        row = i//n
        col = i%n
        num = max(row,col)+1
        arr.append(num)
    return arr