[Programmers] Lv. 2 n^2 배열 자르기

문제

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

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

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

---

제한사항

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

프로그래머스

 

입출력 예시

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

 

입출력 예 설명

입출력 예 #1

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

 

입출력 예 #2

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

 

풀이 코드

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

 

풀이

문제 구현 자체는 어렵지 않다.

하지만, 이 문제는 런타임 에러가 가장 큰 어려운 문제이다.

n이 10^7까지 가능하기에 단순하게 중첩 for문으로 문제를 풀면 거의 모든 테스트에서 런타임 에러 문제로 실패할 것이다.

그렇기 때문에 규칙을 찾아 left에서 rigth 범위에 대해서만 구할 수 있어야 한다.

내가 찾은 규칙은 다음과 같다.

n = 3인 경우로 예시를 들도록 하겠다.

n이 3인 경우에 대한 배열 인덱스는 다음과 같다.

(0, 0)	(0, 1)	(0, 2)
(1, 0)	(1, 1)	(1, 2)
(2, 0)	(2, 1)	(2, 2)

 

그리고 문제에서 만들라고 한 2차 배열은 다음과 같다.

1	2	3
2	2	3
3	3	3

 

위와 같은 표를 확인했을 때 2차 배열의 각 값은 행과 열 인덱스 중 더 큰 값에 더하기 1을 한 값이다.

 

첫 번째 규칙은 찾았다.

그런데 문제는 중첩 for문을 사용하지 않고 오로지 left에서 right 범위에 대한 값만 구해야 한다는 점이다.

그냥 값을 0부터 순서대로 각 위치에 넣으면 아래와 같다.

* 규칙 설명에서 이 값을 i라고 하겠다.

0	1	2
3	4	5
6	7	8

 

해당 칸의 인덱스를 구하기 위한 규칙은 다음과 같다.

2차 배열 행 : i // n

2차 배열 열 : i % n

 

그러므로 우리는 left ~ right 구간에 대해서만 행과 열의 값을 구해 둘 중 큰 값에 더하기 1한 값을 answer 배열에 추가하면 된다.