일단 코드부터 짜는 나쁜 버릇을 고치고, 시간 복잡도를 잘 고려하여 풀기 위해 코테 풀이 과정을 남긴다!
해당 문제는 문제 설명 과정대로 풀면 시간초과가 나고, 어떻게 효율적으로 '답을 구할지'를 잘 생각해서 풀어야 하는 수학문제다.

문제

문제 설명

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

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ n ≤ 10^7
0 ≤ left ≤ right < n2
right - left < 10^5

풀이 과정

1. 문제 서술대로 풀이(시간 복잡도 고려 x)

아이디어

이차원 배열을 만들고, 문제에서 주어진 것처럼 각 행의 값을 채운다. 첫 줄은 1,2,3.. 순서대로, 그 다음 줄은 1을 없애고 2를 2개 이렇게 채우면 된다. 따라서 먼저 각 행을 1~n까지로 채운 뒤, 그 행의 번호에 맞게 숫자를 채워나가면 된다. 무슨말이냐면, 2번째 줄이면 2라는 숫자를 앞에서부터 2개, 3번째 줄이면 3이라는 숫자를 앞에서부터 3개 채운다.

구현

def solution(n, left, right):
    arr = [[] for _ in range(n)] 
    oneDimension= ''
    
    for i in range(n) :
        arr[i] = list(range(1,n+1))
        for j in range(i) :
            arr[i][j] = i+1
            ## i번째 줄이면 i+1의 값으로 i번 동안 채운다. 
        oneDimension += ''.join(map(str,arr[i]))

    return list(map(int,oneDimension[left:right+1])) 

문제점

하지만 이렇게 풀면 시간복잡도에서 문제가 생긴다.

2. 시간복잡도를 고려한 풀이

아이디어

결국 구해야 하는 값은 left~right 까지의 인덱스다. 그리고 문제가 주어진 조건 자체가 특정한 규칙성을 띄기 때문에 이를 다른 각도로 답에 대한 규칙을 찾으면 더 간단히 풀 수 있다.
일렬로 나열했을 때의 index를 n으로 나눈 몫, 나머지를 통해 이차원 배열로 표현했을 때의 행, 열을 구할 수 있다.

left // n => 열
left % n => 행

그리고 각 행과 열에 채워지는 값은, 결국 행과 열의 최댓값 +1이다. 예를들어, 0행 1열이면 0과 1의 최댓값은 1이고, 인덱스가 0부터 시작이니까 +1을 한 값으로 채워진다.

이렇게 되면, left~right까지 for문을 한 번만 돌면 구현이 가능하다. 이렇게 되면 시간복잡도 문제가 사라진다는 것을 문제 조건에서도 알 수 있다. 10의 5제곱번이니 2천만번보다 연산 횟수가 적게 되고, 시간이 1초여도 게산 가능하다.

right - left < 10^5

구현

다음과 같이 구현할 수 있다.

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


    return answer