[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ n^2 배열 자르기

https://programmers.co.kr/learn/courses/30/lessons/87390

코딩테스트 연습 - 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

[아이디어]

1) 제한 조건의 숫자들이 좀 크다..

2) 각 row의 규칙성을 활용할 수 있을 것 같다.

3) 어마어마한 숫자를 봤을 때, 문제 처럼 배열을 만든 뒤 일부를 잘라내는 것이 아니라 처음 부터 해당 부분만 구현해야 하지 않을까.

4) left와 right을 n으로 나눈 몫과 나머지가 역할을 할 수 있을 것 같다.

# 시간 초과
def solution(n, left, right):
    answer = []
    for i in range(1, n+1):
        answer += ([i]*i + list(range(1, n+1))[i:])
    return answer[left:right+1]

역시나 시간 초과가 났다. 다루는 숫자의 크기가 너무 커서 전체를 다 구현한 뒤 일부를 slicing 하는 것은 효율이 좋지 못하다. 따라서 left, right를 n으로 나눈 몫과 나머지를 이용해 필요한 부분만 구현하는 것이 좋다.

# 통과
def solution(n, left, right):
    answer = []
    a, b = left//n +1, left%n
    c, _ = right//n +1, right%n
    for i in range(a, c+1):
        answer += ([i]*i + list(range(i+1, n+1)))
    return answer[b:b+right-left+1]

아래처럼 위치를 n으로 나누었을 때의 몫과 나머지를 다르게 이용한 풀이도 있었다. 반복되는 숫자에 대한 표현을 max로 한 것이 인상적이다. 이런 생각은 어떻게 하지..

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