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

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

문제보고 쉽다고 생각했는데,, 생각보다 어려웠던 문제이다.

어찌어찌해서 풀긴 했는데 코드가 일단 가독성도 떨어지고, 

30점 받고 대부분의 히든케이스는 시간초과..

# 시간 초과 코드
"""
def solution(n, left, right):
    answer = [[0]*(n) for _ in range(n)]
    ans = []
    for i in range(n):
        for j in range(n):
            if (i+1)*(j+1) <= (i+1)**2:
                answer[i][j] = i+1
            else : 
                answer[i][j] = answer[i][j-1] +1
            ans.append(answer[i][j])  

    return ans[left:right+1]
"""

시간 초과가 난 이유 :

솔직히 내가 봐도 메모리든 시간이든 초과될 것 같았슴.. 문제를 처음 보고,

2차원 배열을 만들고 다시 1차원 배열로 잘라서 left~right 인덱스를 뽑을거면 굳이 2차원 배열을 만들 필요가 있나? 싶어서 1차원 배열로 만들려고 했으나 실패ㅎ..

그래서 2차원 배열로 만들어주었음 (1차 낭비)

그리고 이제 left~right 인덱스를 뽑아줘야하는데... 2차원 배열에서 어떻게 뽑아야할지 몰라서 1차원배열에 2차원배열값을 하나씩 추가해줌^^^ (2차 낭비)

그래서 시간초과났다..................

애초에 

[ [1, 2, 3]

  [2, 2, 3]

  [3, 3, 3] ]  <= 이 배열을 만드는 공식도 이상해서 맘에 안 들었다...............

 

<< 풀이 >>

n이 3이면 다음과 같이 배열이 만들어질 것

(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

(0,0)이면 1, 인덱스에 1이 한 개라도 들어가면 2, 인덱스에 2가 한 개라도 들어가면 3이다.

그러므로 해당 위치의 값 = max (해당 위치 // n , 해당 위치 % n) + 1이다.

왜냐하면 해당 위치 // n == i, 해당 위치 % n == j 이므로 i와 j 인덱스 중 큰 인덱스의 +1 이 값이 되는 것...

진짜 대박이다....

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

    for i in range(left, right + 1):
        answer.append(max(i // n, i % n) + 1)

    return answer

그래서 코드는 위와 같이 만들어진다.

answer 전체의 1차원 배열도 만들 필요가 없었던 것.. 그냥 left~right 위치까지만 반복문을 돌리면 됐던 것임..