프로그래머스: n^2 배열 자르기 (파이썬, 구현)

규칙만 알면 금방 풀 수 있는 문제라 생각한다. 먼저 제한사항부터 보면 n의 최댓값이 10^7이다. 만약 2차원 배열을 2중 반복문으로 일일히 초기화하여 푼다면 시간복잡도가 10^14이상으로 시간초과가 날 것이다. (일반적으로 시간복잡도는 10^9를 넘기지 않아야 한다.) 따라서 2차원 배열을 직접 만들어서 풀수는 없고 다른 풀이를 생각해야 한다.

 

테스트케이스 설명을 애니메이션으로 아주 현란하게 설명하는 문제였는데 나는 그런건 할줄 몰라서 파워포인트로 간단하게 그림을 그려 설명해보겠다.

 

테스트 케이스2의  n=4인 2차원 배열이다. 왼쪽에 숫자는 배열에 채워지는 수들이고 괄호안의 숫자는 배열의 몇번째에 있는지를 나타낸 것이다. 문제에서 주어지는 left와 right가 괄호안의 숫자에 해당함을 알 수 있다.

 

이때 괄호안의 숫자를 n으로 나눈 몫이 행이 되고 나머지가 열이 됨을 알 수 있다. 예를 들어 7을 4로 나눈 몫은 1, 나머지는 3이고 #7은 (1,3)에 위치하는 것을 볼 수 있다.

 

마지막으로 열의 위치가 행의 위치보다 크다면 괄호안의 수는 열의 위치를 따른다는 것을 표를 봄으로써 알 수 있다. 이 내용들로 짠 코드는 다음과 같다.

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