LV2 n^2 배열 자르기

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87390?language=python3 

프로그래머스

풀이

만약 n*n배열을 모두 만들어서 값을 추출하려하면 메모리 초과 + 시간초과가 걸릴것이다. (n은 최대 1000만인데, n*n은 답도 없다.) 따라서 문제의 핵심은 left부터 right 값만 구하는 것이다. right - left는 최대 10만으로 명시되어 있기에 시간이나 메모리에 걸릴일이 없다.

 

2차원적으로 생각해서 시작하는 행과, 끝나는 행을 구할필요가 있다고 생각했다. 곰곰히 확인해보니 left/n이 시작하는 행이고, right/n이 끝나는 행이었다. 그리고 left%n이 시작하는 행의 시작하는 열이고, right%n은 끝나는 행의 열이였다.

 

이 정보를 토대로 시작하는 행부터 끝나는 행까지 값을 우선 만들어주고 (아래의 for문 과정), 끝나는 행의 열 번호를 일차원으로 변형한 값을 활용하여 답을 냈다.(변수 ei)

 

코드

def solution(n, left, right):
    answer = []
    sr = left//n
    er = right//n
    
    sc = (left%n) 
    ec = (right%n)
    
    ei = n*(er-sr) + ec
    
    for i in range(sr+1, er+2):
        j = i
        for k in range(1, n+1):
            if k>i:
                j += 1
                answer.append(j)
            else:
                answer.append(j)
    return answer[sc:ei+1]

 

후기

 

난 저 for문이 굉장히 복잡하면서도, 쓸모없는 부분까지 만들기에 굉장히 별로라고 생각했다.

아니나 다를까, 다른 풀이를 보니 인덱스에 들어가는 값은 max(행, 열) 로 구할 수 있었다.

첫번째 예시의 right를 보면 2차원으로는 (1,2) 의 좌표를 가지고 값은 3인데 max(1, 2) + 1 의 값이 되는것이었다.

 

저기까지 생각했더라면 베스트겠지만, 행과 열을 나누기와 나머지로 찾은거 정도로도 만족은 한다..