n^2 배열 자르기
문제 설명
- n 행 n 열 크기의 2차원 배열이 주어진다.
- 2차원 배열을 1차원 배열로 변환한다.
- left, right 인덱스가 주어지면 1차원 배열에서 left, right 에 해당하는 원소를 구한다.
1차원 배열로 만든 후 left, right 만큼의 해당 원소를 찾아라
흐름 파악
흐름 파악을 위해 꼬리에 꼬리를 무는 방식으로 접근하려한다.
left ~ right 까지의 원소를 구하는 방법
1차원 배열로 펼치고 left ~ right 까지의 원소를 구하면 돼.
다 펼치고 구할 때 시간 복잡도는?
n 행 n 열이니까 O(n^2) 이야.
n 의 최대 값은 10^7 이니까 최대 10^14 의 시간이 걸려. 10^14 의 값은 100조이야. 절대 펼치면 안되곘어.
바로 구할 수 있는 방법은?
n=3, left=2, right=5 일 때를 보자. 아래와 같은 규칙을 찾을 수 있다.
2 = [0, 2] = [2 // 3, 2 % 3]
3 = [1, 0] = [3 // 3, 3 % 3]
4 = [1, 1] = [4 // 3, 4 % 3]
5 = [1, 2] = [5 // 3, 5 % 3]
전체 코드
def solution(n, left, right):
answer = []
def calc_value(row, col):
return max(row, col) + 1
for i in range(left, right + 1):
answer.append(calc_value(i // n, i % n))
return answer
