n^2 배열 자르기 [Python]

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

문제 설명

• 정수 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 ≤ 107
• 0 ≤ left ≤ right < n2
• right - left < 105

문제 풀이

1) 전체 배열을 만든뒤 left와 right의 범위 값을 index하는 방식

• 문제에서 말한것처럼 처음 1차원 배열을 만들고, 1차원 배열에서 +1씩 하는 코드를 작성하였다.
• 하지만 input의 길이가 너무길어서 위의 solution은 시간 초과가 된다.

2) 좌표의 규칙을 이용한 정답

• 1 2 3으로 만드는 행렬을 보게 되면 각 좌표(row, col)에 해당되는 값이 좌표의 max값 +1인걸 알수있다.
• (1,0)의 값은 max 1의 + 1인 2로 되고, (2,2)의 값은 max 2의 + 1인 3이 된다.
• 그럼 left와 right의 값을 각 좌표로 치환을 하고, 해당 좌표의 max + 1을 하게된다면 굳이 모든 배열을 만들지 않아도 결과값을 볼수 있다.
• 해당 좌표값은 python의 divmod를 활용하여 주어진 n을 left와 right의 범위 x로 나누면 몫은 row, 나머지는 col로 나오게 된다.
  • 4 * 4 (n=4)의 정방행렬에서 x=7인 좌표를 구하자면 divmod(7, 4)를 사용하여 좌표값 (1,3)을 구하게 되고, 해당 위치의 값은 max(1,3) + 1 인 4가 된다.
• 위의 방법을 left와 right의 범위만큼 (python의 range는 설정 범위의 하나 아래까지 보이니 right는 +1를 해줘야함) 값을 구하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 시간초과

def plusone(x):
     return x + 1

def solution(n, left, right):
    arrs = []
    arr = [i for i in range(1, n +1)]
    arrs.extend(arr)
        
    
    for j in range(1,n):
        arr[:j] = list(map(plusone ,arr[:j]))
        arrs.extend(arr)
    
    return arrs[left:right+1]

1
2
3
4

n = 3
left = 2
right = 5
solution(n, left, right)

1

[3, 2, 2, 3]

1
2
3
4

n = 4
left = 7
right = 14
solution(n, left, right)

1

[4, 3, 3, 3, 4, 4, 4, 4]

1
2
3
4
5
6
7

# 좌표로 생각

def solution(n, left, right):
    results = []
    for x in range(left, right+1):
        results.append(max(divmod(x, n)) + 1)
    return results

1

divmod(7,4)

1

(1, 3)

1
2
3
4

n = 3
left = 2
right = 5
solution(n, left, right)

1

[3, 2, 2, 3]

1
2
3
4

n = 4
left = 7
right = 14
solution(n, left, right)

1

[4, 3, 3, 3, 4, 4, 4, 4]