[Programmers] n^2 배열 자르기

문제

링크 (문제 설명이 말로 하기가 까다로워서, 직접 문제에 들어가 GIF를 보는 것이 이해가 더 빠르다)

 

n x n 크기의 2차원 배열을 특정 규칙에 따라 채운 뒤, 이를 1차원 배열로 펼쳤을 때 left부터 right까지의 구간만 반환하는 문제. n은 최대 10^7까지 주어지고, right - left는 10^5 미만으로 제한된다.

 

처음 보면 2차원 배열을 직접 만들어야 할 것 같지만, n^2 크기의 배열을 만드는 순간 시간과 메모리 양쪽에서 바로 터지는 문제로, 결국 전체 배열을 만드는 것이 아니라 특정 인덱스가 원래 2차원 배열의 몇 행 몇 열인지 계산해서 값을 바로 구해야 하는 문제다.

 

회고

솔직히 처음에는 '설마 바로 값을 찍어야 하는 문제는 아니겠지'라고 생각했는데, 그게 정답이었다. 제한 조건을 보면 애초에 리스트를 만든 다음에 자르는 행위가 불가능한데, n이 최대 10^7이기 때문에 n x n 배열은 최대 10^14칸이기 때문. 핵심은 1차원 인덱스를 다시 2차원 좌표로 바꾸는 것으로, 어떤 인덱스 i가 있을 때, 행은 i // n, 열은 i % n으로 구할 수 있고, 문제에서 만들어지는 배열을 직접 찍다보면 어떻게든 규칙이 나오기는 나오는데, 그저 행과 열 값 중에 더 큰 값을 넣으면 된다는 조건. (다만 이 문제에서는 0, 0부터 시작하는 게 아니다 보니 각각 row와 col에 1을 더해줬다) 제한 조건만 보고 빠르게 전체를 만들 생각은 저버리고 필요한 부분만 수식 계산이 되는지 의심해 봐야 했던 문제.

def solution(n, left, right):
    answer = []

    for i in range(left, right + 1):
        row = i // n + 1
        col = i % n + 1
        answer.append(max(row, col))

    return answer