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

프로그래머스 월간 코드 챌린지 3에 출제된 Level 2 난이도의 문제다. 

 

 

초기 풀이는 extend를 활용해서 아래와 같이 작성하였다. 

def solution(n, left, right):
    ans = []
    for i in range(n):
        l = list(range(i+1, n+1))
        ans.extend([l[0]]*(n-len(l)) + l)

    return ans[left:right+1]

일부 케이스에서는 통과가 되었으나, 시간 초과가 발생한다. list를 생성하고 extend하는 과정에서 오래 걸리는 것으로 확인된다.  시간 복잡도를 줄이기 위해 몫, 나머지 개념을 도입했다. 

 

(0, 0)	(0, 1)	(0, 2)	(1, 0)	(1, 1)	(1, 2)	(2, 0)	(2, 1)	(2, 2)
1	2	3	2	2	3	3	3	3

3x3 행렬 기준, 값을 풀어서 생각하면 위와 같은 표로 표현할 수 있다. index를 n으로 나누었을 때 몫과 나머지 중 큰 값을 반환하고 1을 더하게 되면 아래와 같은 값을 도출할 수 있다. left와 right+1 을 제외한 나머지 구간에서는 값을 계산할 필요가 없기 때문에 해당 구간에 대해서 코드로 표현하면 다음과 같다. 

def solution(n, left, right):
    answer = []
    for i in range(left, right+1):
        a, b = i//n, i%n        
        answer.append(max(a,b)+1)
    return answer