Programmers - n^2 배열 자르기 [Python3]

📣 문제 설명

정수 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]만 남기고 나머지는 지웁니다.

📌 제한사항

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

📌 입출력 예

✏️ 문제풀이

첫 시도 🐣

1. n*n 형태의 2차원 배열에 문제 로직에 따라 값을 집어넣는다.
2. 만든 배열의 left ~ right 까지의 원소를 구해 answer 리스트에 하나씩 넣는다.

2차원 배열을 아래 코드로 초기화하고, 😏

arr = [[0]*n]*n]

배열 안에 값을 집어 넣었는데..!
웬걸, 배열이 이상하게 만들어지는 것이었다! 😱
원소 넣는 로직이 잘못된 것은 아닌지 디버깅을 해보았으나,
버그를 찾아내지 못하였다.....또륵
그래서 혹시나 하는 마음에, 파이썬 2차원 배열 선언 방법을 구글링했더니

Python에서는 * 연산자를 이용해 배열을 선언하게 되면, 얕은 복사(shallow copy)가 진행된다.
즉, 배열 내의 요소들이 같은 객체를 가리키게 되는 것이다.
따라서, 이 방식으로 2차원 배열을 선언하고 요소를 변경하게 되면 다른 요소들의 값도 같이 바뀌는 것이다.

라고 설명하는 포스팅을 발견하였다..ㅎㅎ

🎈 파이썬에서 2차원 배열을 선언하는 방법 🎈

arr = [[0 for j in range(cols)] for i in range(rows)]

• rows: 행 개수
• cols: 열 개수

로직을 모두 구현하고 코드가 잘 실행되는 것을 확인한 후,
제출하기를 눌렀는데 절반 정도의 테스트케이스에서 시간 초과가 발생하였다 ㅜㅜ

두번째 시도 🐥

2차원 배열을 만드는 과정에서 2번의 for 문을 실행하기 때문에 시간초과가 발생한다고 생각하였다.

그렇다면, 모든 배열을 만들지 않고 정답을 찾을 수 있는 방법을 생각해 보기로 하자.
우리에게 필요한 것은 left 번째 원소부터 right 번째 원소까지 이다.
각 원소와 좌표 간의 관계를 다시 따져 보니,

x 좌표가 y좌표보다 작을 경우 (x>y), 원소는 y+1이고
x 좌표가 y좌표보다 크거나 같을 경우 (x<=y), 원소는 x+1의 값을 가진다.

이 관계를 활용하여 left ~ right 까지의 원소를 구하였다.

👩🏻‍💻 제출 코드

def solution(n, left, right):
    answer = []

    x = int(left/n)
    y = left%n
    # print('x = ', x, 'y = ', y)
    for i in range(right-left+1):
        if y == n:
            y = 0
            x += 1

        if x < y: 
            answer.append(y+1)
        else:
            answer.append(x+1)
        y += 1
    return answer