Programmers / n^2 배열 자르기 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: n^2 배열 자르기 (2단계) 

 

문제 사이트: https://programmers.co.kr/learn/courses/30/lessons/87390

 

문제 설명

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

---

입출력 예nleftrightresult

3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

---

입출력 예 설명

입출력 예 #1

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

---

Numpy를 활용한 풀이

나의 풀이

*시간 복잡도와 공간 복잡도를 고려하지 않은 순수 라이브러리 활용 풀이입니다!!!!

 

일단 처음에 넘파이를 이용해서 문제를 풀 수있을 거 같아서 풀어봤다!

 

import numpy as np

def solution(n,left,right):
    A = np.ones((n,n), dtype = int)

    for i in range(n,0,-1):
        for j in range(i):
            for k in range(j):
                A[k][j] = i
                A[j][k] = i

    for i in range(n):
        A[i][i] = i+1

    arr = A.flatten()
    return arr[left:right+1]
n = int(input())
left = int(input())
right = int(input())
print(solution(n,left,right))

 

1. A 행렬을 만들어서 np.ones 를 통해 nXn 행렬을 만들어준다! 그러면 nXn 행렬에 1이 채워져서 저장이된다.

A = np.ones((n,n), dtype = int)

2.  문제의 그림대로 행렬에 숫자를 저장한다.

for i in range(n,0,-1):
    for j in range(i):
        for k in range(j):
            A[k][j] = i
            A[j][k] = i

for i in range(n):
    A[i][i] = i+1

이렇게 중첩 for문을 통하여 그림과 똑같이 행렬을 만들어주었다.

3. 넘파이 라이브러리의 flatten 을 이용하여 벡터로 변환한다.

    arr = A.flatten()

 

벡터로 변환한 모습

    return arr[left:right+1]

최종적으로  left와 right 범위만큼 반환한다

그림에서 요구하는 결과값과 같은 것을 볼 수 있다.

근데 실행이 안된다........!!!!

 

실행이 안되는 이유는 바로, 넘파이로 저장된 1차원 벡터가 리스트의 형태로 출력이 되지 않아서이다.

따라서 이 벡터를 1차원 리스트로 변환해야한다.

    arr = A.flatten()
    answer = arr[left:right+1].tolist()

리스트로바꿀어레이.tolist() 함수를 이용해서 리스트로 변환시켜주면 된다! ㅎㅎ

올바르게 출력된 모습

최종 풀이

import numpy as np

def solution(n,left,right):
    A = np.ones((n,n), dtype = int)

    for i in range(n,0,-1):
        for j in range(i):
            for k in range(j):
                A[k][j] = i
                A[j][k] = i

    for i in range(n):
        A[i][i] = i+1

    arr = A.flatten()
    answer = arr[left:right+1].tolist()
    return answer

이렇게 풀면 테스트는 풀리지만, 최종 채점에는 런타임에러가 난다 ㅠ,ㅠ

아무래도 라이브러리를 가져와서 풀어서 연산 시간이 오래걸리는거 같다.

 

 

다른 풀이 (규칙 이용)

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

    return answer
 
print(solution(3, 2, 5)) # [3,2,2,3]

[1, 2, 3, 4, ...]

[2, 2, 3, 4, ...]

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

[4, 4, 4, 4, ...]

.

.

.

 

로 진행하는 배열로 규칙을 찾아서 구해주면 된다.

위치를 i 라고 한다면 i 를 n 으로 나누면 i 에 해당하는 행과 열을 구할 수 있다.

위의 규칙으로 봤을 때 해당하는 행과 열의 위치에 있는 값은 max(행, 열) + 1 이라고 할 수 있다.