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

📝 문제

풀이

❌ 런타임 에러

2차원이 아니라 1차원 배열을 만들어서 슬라이싱 하려고 했는데 n은 최대 10^7까지 될 수 있다. 아무리 1차원이어도 10^14의 길이는 = 거의 10조...?

def solution(n, left, right):
    answer = [x for x in range(1, n+1)]*n
    
    interval = 1
    while n*interval<=right and n*interval<len(answer):
        for t in range(interval):
            answer[n*interval+t] = interval+1
        interval += 1 
        
    return answer[left:right+1]

💡 풀이 아이디어

2차원 배열의 각 칸에 들어간 숫자들이 어떤 규칙을 갖고 들어가 있는지 생각해봐야 한다.

(1, 1) → 1

(2, 1) → 2
(2, 2) → 2
(1, 2) → 2

(3, 1) → 3
(3, 2) → 3
(3, 3) → 3
(2, 3) → 3
(1, 3) → 3

각 칸에 들어가게 되는 값 : (y, x) 중 더 큰 값

각 칸의 행(y)은 현재 칸을 1차원 배열로 만들었을 때 갖게 되는 인덱스를 n으로 나눴을 때의 몫, 각 칸의 열(x)은 나머지가 된다. 모든 값은 0부터 시작하기 때문에 최종적으로 값에 1씩 더해주면 됨.

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