[프로그래머스] n^2 배열 자르기 - Python

이번에 해결해 볼 문제는 프로그래머스에 있는 n^2 배열 자르기이다.

---

문제 설명

1. n행 n열 크기의 비어있는 2차원 배열을 만들고 아래와 같이 배열을 채운다.

2. 1행 ~ n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만든다.

3. 새로운 1차원 배열을 arr이라고 할 때 arr[left:right+1]을 출력하면 된다.

문제 해결 아이디어

1. 해당 문제를 처음 접하고 제한사항을 고려하지 않으면 시간초과가 뜰 수 밖에 없는 문제이다.

   • 해당 문제에서 주어진 제한사항을 자세히 살펴보면 right - left < 10^5로 right와 left의 범위를 어느 정도 제한해 주었다.
   • 따라서 2차원 배열을 직접 만들고 1차원 배열로 펼치고 left부터 right까지 자르는 구현은 해당 문제에서는 적합하지 않다.

2. 2차원 배열이 있을 때 해당 배열은 행과 열로 표현할 수 있지만 하나의 숫자로 구분하여 표현할 수 있다.

   • n x n의 배열이 있을 때 i행 j열의 원소는 i*n + j와 같다.
   • 따라서 left와 right는 (left//n, left%n), (right//n, right%n)으로 표현 가능하다.

3. 결론적으로 문제에서 설명한 순서대로 구현하는 것이 아니라 직접 1차원 배열을 구현해야 시간초과가 뜨지 않고 정답을 맞출 수 있다.

문제 해결 코드

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

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

    return answer