[프로그래머스/Level2/파이썬3(python3)] n^2 배열 자르기

[프로그래머스/Level2/파이썬3(python3)] 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

입출력 예

n	left	right	result
3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

풀이

def solution(n, left, right):
    answer = []
    for number in range(int(left), int(right)+1):
        quotient, remainder = divmod(number, n)
        answer.append(quotient + 1 if quotient > remainder else remainder + 1)
    return answer

설명

꽤나 고생했던 문제이다. 총 세번의 구현이 있었는데

첫번째 구현

def solution(n, left, right):
    matrix = [[0 for _ in range(n)] for _ in range(n)]
    for number in range(1, n+1):
        for col in range(number):
            for row in range(number):
                matrix[col][row] = number if matrix[col][row] == 0 else matrix[col][row]
    for row in matrix:
        flat += row
    return flat[left:right+1]

다소 러프하게 후다닥 짠 코드이다. 애초에 2차원배열을 색칠하는 것 자체가 굉장히 비효율적이지만 로직만 맞는다면 어차피 정답이겠거니 하고 제출해봤고 당연히 시간초과났다. 그래서 아 역시 색칠하는 부분(숫자를 채우는 부분)만 수정하면 되겠거니 해서 배열에 숫자를 채우는 부분만을 새로 개선해 두번째로 제출을 했다.

두번째 구현

def solution(n, left, right):
    flat = []
    matrix = []
    n_list = list(range(1, n+1))
    for index in n_list:
        temp_list = n_list[index:]
        numbers = [index] * index
        matrix.append(numbers + temp_list)
    for row in matrix:
        flat += row
    return flat[left:right+1]

배열에 숫자를 넣는 부분에서 로직 낭비를 없앴지만 역시나 시간초과가 났다. 그래서 혹시 몰라 list slicing하는 부분만 return [1,2,3,4]로 바꿔봐도 시간초과가 나길래 애초에 배열을 채워넣는 행위 자체가 문제의 의도가 아니라는 걸 확인했다. 규칙을 찾아서 해결해야하는 문제인 것을 깨달은 순간이다.

세번째 구현

def solution(n, left, right):
    answer = []
    for number in range(left, right+1):
        quotient, remainder = divmod(number, n)
        answer.append(quotient + 1 if quotient > remainder else remainder + 1)
    return answer

입출력 예제 1로 로직을 설명해보자면 이렇다.

0,0 [1]	0,1 [2]	0,2 [3]
1,0 [2]	1,1 [2]	1,2 [3]
2,0 [3]	2,1 [3]	2,2 [3]

좌측엔 좌표, 오른쪽엔 해당 좌표에 실제로 있어야하는 값을 의미한다. 규칙을 보면 알겠지만 두 좌표 중에서

1. 0과 0밖에 없다면 1
2. 1이 하나라도 있다면 2
3. 2가 하나라도 있다면 3이 되는 것을 확인할 수 있다.

고로 두 좌표 사이에서 큰 수 + 1이 해당 좌표에 들어가야할 값이라는 걸 확인할 수 있다. 규칙을 확인한 이상 1차원화시킬 필요도, 2차원배열을 만들 필요도 없다. 좌표 두개의 값만 확인할 수 있으면 해당 위치에 들어가야 할 값을 알 수 있으니 말이다.

 

좌표 리스트들은 어떻게 구할까, 몫과 나머지로 구할 수 있다. 좌표가 출력되는 모습이 궁금한 사람은 quotient, remainder = divmod(number, n)이 라인 밑에 print해보면 쉽게 이해가 갈 것이다. 그렇게 두 좌표중 커다란 좌표의 index + 1을 하면 그 안에 들어가야할 값을 얻을 수 있어서 배열을 실제로 만들지 않고도 해당 문제를 해결할 수 있다. 오히려 입출력 예제에 있는 gif로 된 것이 함정인 문제였던 것이었던 것이었던 것이었다.