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

문제

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

소스코드

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

    return answer

설명

처음에 정말로 문제에서 하라는 대로 구현했더니 시간초과가 발생했다.

n의 최댓값이 10^7이기 때문에 당연하다 ^^.. 

def solution(n, left, right):
    # 배열 만들기
    answer = [[0] * n for _ in range(n)]
    # 배열에 값 넣기
    for i in range(1,n+1):
        for j in range(1,n+1):
            answer[i-1][j-1] = max(i,j)
    # 1차원 배열로 만들기
    tmp_arr = []
    for i in range(n):
        tmp_arr += answer[i]
    #left ~ right 까지 출력
    return tmp_arr[left:right+1]

그래서 시간초과를 해결할 수 있도록 생각을 다르게 바꿔보았다.

1. 이차원 배열에 원소를 넣고 일차원 배열로 만들지 말고 처음부터 일차원 배열을 계산한다.
2. n까지 가지 않고 정말 필요한 left ~ right 까지만 계산한다.

문제에서 주어진 N = 3 인 경우를 생각해보자.

값 , 우리가 구해야하는 값

0 => 1	1 => 2	2 => 3
3 => 2	4 => 2	5 => 3
6 => 3	7 => 3	8 => 3

 

값 // N , 값 % N 

0 , 0	0 , 1	0 , 2
1 , 0	1 , 1	2 , 2
2 , 0	2 , 1	2 , 2

위의 표를 보면 값의 몫이나 나머지 중 큰 값 + 1 을 하면 우리가 원하는 값을 도출해낼 수 있다.