[Python] n^2 배열 자르기

✏️ 문제

 

문제 파악

처음에는 이중 for 반복문 써서 풀었는데 역시나.. 시간초과로 통과가 되지 않았다.

그럼 규칙을 찾아야 하는데 첫 번째 예시를 보면 다음과 같다.

i \ j	0	1	2
0	0, 1 = 1	1, 2 = max(i, j) + 1	2, 3 = max(i, j) + 1
1	3, 2 = max(i, j) + 1	4, 2 = max(i, j) + 1	5, 3 = max(i, j) + 1
2	6, 3 = max(i, j) + 1	7, 3 = max(i, j) + 1	8, 3 = max(i, j) + 1

 

위의 표에서 파란색 숫자는 1차원 배열로 만들었을 때 left와 right의 기준이 되는 숫자를 말한다.

전체적으로 봤을 때 해당 index의 값은 가로와 세로 index 중 max(index) + 1로 이뤄지는 것을 알 수 있다.

 

이때 가로 index(표에서 j)와 세로 index(표에서 i)를 구해야하는데 이때 주어지는 건 n과 left, right 값이므로 다음과 같이 구성된다.

i = (1차원 배열에서의 값) // n
j = (1차원 배열에서의 값) % n

 

1차원 배열에서의 값은 left와 right를 활용해서 넣으면 된다.

 

이 문제를 푸는데 중요한 것은 

for 반복문이 2차원 배열 전체를 돌지 않고 left와 right 사이만 돌면 된다.

 

 

코드

• 시간초과 코드

def solution(n, left, right):
    answer = []
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            if j < i:
                temp = i
                answer.append(temp)
            else:
                answer.append(j)
    
    return answer[left:right+1]

• 통과 코드

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