Lv2. n^2 배열 자르기

[n^2 배열 자르기]

문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
3. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
4. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
5. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

1 ≤ n ≤ 107
0 ≤ left ≤ right < n2
right - left < 105

---

입출력 예

n left right result
3 2 5 [3,2,2,3]
4 7 14 [4,3,3,3,4,4,4,4]

---

실패한 풀이

import numpy as np

def solution(n, left, right):
    answer = []
    square = np.zeros([n,n], dtype=int)
    # initialize 2D array
    for i in range(n-1, -1,-1):
        square[:i+1,:i+1] = i+1
    # flatten
    flatsquare = square.flatten()
    return flatsquare[left:right+1].tolist()

시간초과로 실패한 코드.. 정말 정직하게 문제의 내용을 코드로만 구현했기 때문에 시간이 초과되었다. 특히 처음에 initialize 하는 부분에서

    for i in range(n-1, -1,-1):
        square[:i+1,:i+1] = i+1

이렇게 코드를 짜서 거꾸로 정사각형 모양으로 수를 전부 채워나가는 식으로 접근했는데, 그것보다는 좀 더 수학적으로 분석을 한 후에 풀이를 적어나가는 것이 좀 더 훌륭했을 것 같다
계속 문제를 들여다보다 보니 각 셀의 값을 저렇게 위치로 하는 게 아니라 flatten 됐다고 가정한 row 1짜리 array에서도 찾을 수 있는거였다 그 방법을 이용해서 한번 다시 해봤다

성공한 풀이

내 풀이

def solution(n, left, right):
    answer = []
    #range를 n**2로 설정하여 전 범위를 다루게 되면 시간이 너무 길어져서 최소화했다
    for i in range(left,right+1):
        a = i//n
        b = i%n
        if a>=b: 
            answer.append(a+1)
        else:
            answer.append(b+1)
    return answer

다른 사람 풀이1

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

내가 한 풀이와 결이 크게 다르지 않은 풀이. 푼 사람들 중 대부분이 이렇게 푼 것 같다

solution = lambda n, left, right: list((max(i // n, i % n) + 1 for i in range(left, right + 1)))

한줄짜리 코드.. 나는 예나 지금이나 람다는 잘 못쓴다 신기해서 가져와봤다 사실 볼때마다 신기해서 가져오는거 같긴 하다