[프로그래머스/Lv2] n^2 배열 자르기

문제

정수 n, left, right가 주어진다.

다음 과정을 거쳐서 1차원 배열을 만들고자 한다.

 

1. n행 n열 크기의 비어있는 2차원 배열을 만든다.

2. i = 1, 2, 3, ..., n 에 대해 다음 과정을 반복한다.

   -> 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채운다.

3. 1행, 2행, 3행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만든다

4. 새로운 1차원 배열을 arr이라 할 때, arr[left]~arr[right]만 남기고 나머지는 지운다.

 

주어진 과정대로 만들어진 1차원 배열을 반환하는 함수를 만들어야 한다.

 

 

제한사항

1. 1 <= n <= \(10^7\)

2. 0 <= left <= right <= \(n^2\)

3. right - left < \(10^5\)

 

 

코드

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

    return answer

 

 

설명

이 문제는 문제에서 설명한 과정 그대로 풀면 십중팔구 시간초과가 날 것이다(n이 \(10^7\)까지 나올 수 있는데 적어도 O(\(n^2\))의 시간복잡도를 가지는 알고리즘을 만들어야 함).

직접 펜을 들고 간단한 숫자 몇 개로 주어진 과정대로 진행해 결과를 만들어보자.

잘 살펴보면 규칙을 찾을 수 있다.

 

n = 3

n이 3일때 주어진 과정 3번까지 진행한 1차원 배열이다.

 

n행 n열의 정사각형 배열이기 때문에 n번 반복하면서 원소가 채워지게 된다.

인덱스에서의 현재 반복횟수는 인덱스에 n을 나눈 몫에 1을 더해주면 얻을 수 있다.

 

이 반복횟수를 인덱스에 n을 모듈러 연산한 값과 비교한다.

인덱스에 n을 모듈러 연산한 값이 현재 그 인덱스의 반복횟수보다 작다면

그 인덱스의 원소는 반복횟수와 같다.

 

나머지 인덱스의 원소는 모두 인덱스에 n을 모듈러 연산한 값에 1을 더한 값이다.

 

이 과정을 그대로 코드로 옮기면 된다.

 

answer = []

정답으로 반환할 배열

 

for index in range(left, right+1):

left부터 right+1까지 숫자들을 꺼내며 반복한다.

 

i = (index // n) + 1

i는 현재 index의 반복횟수를 의미한다.

 

if (index % n) < i:
	answer.append(i)

index에 n을 모듈러 연산한 값이 i보다 작다면

answer에 i를 append한다.

 

else:
	answer.append((index % n) + 1)

그렇지 않다면

answer에 index에 n을 모듈러 연산한 값에 1을 더한 값을 append한다.

 

return answer

answer를 반환한다.