[23회차] n^2 배열 자르기

Programmers Level.2 n^2 배열 자르기

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

 - 시간초과나서 실패.

def solution(n, left, right):
    arr = [0] * (n * n)
    for i in range(n):
        for j in range(n):
            arr[i * n + j] = max(i, j) + 1
    answer = arr[left : right + 1]
    return answer

 - append를 하는게 시간 초과의 원인일 것 같아서 미리 n^2 크기의 배열을 만들었다.

 - 시간초과는 안 뜨는데 그냥 실패.

 

def solution(n, left, right):
    leftx, lefty = left // n, left % n # 시작 index가 몇 행 몇 열인지 파악
    rightx, righty = right // n, right % n # 마지막 index는 몇 행 몇 열인지 파악
    lens = (rightx-leftx) * n + righty - lefty + 1
    answer = [0] * (lens) # answer list를 미리 만들기
    a, b, c = leftx, lefty, 0 # row num, column num, answer index
    while c < lens:
        answer[c] = max(a, b) + 1 # i행 j열에 해당하는 숫자를 answer에 넣기
        if b == n - 1:
            a += 1
            b = 0
        else:
            b += 1
        c += 1
    return answer

 - n의 크기가 10^7라면 n * n 행렬을 만드는 게 시간을 잡아먹는 과정일 것이다.

 - 그 다음에 n * n 행렬을 만들고 다시 n^2 크기의 열벡터로 만드는 것도 비효율적이다.

 

 - 사실 n * n 행렬을 만들 필요가 없었다. 내가 구해야 하는 left ~ right 까지에 해당하는 숫자는 각 index를 행렬로 전환했을 때 몇행 몇열인지만 파악하면 구할 수 있었다. 이를 구현했음.