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