[프로그래머스] Python n^2 배열 자르기 Level2 - 월간 코드 챌린지 시즌3

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

접근

1. 조건에 n의 범위가 상당히 크기 때문에 2중 반복문을 사용하니 시간초과에 걸렸다. 때문에 반복문 하나로 처리하는 방법을 찾아야한다.
2. 규칙을 찾아보자.
   

• 규칙 1. 다음과 같이 i, j 중 가장 큰 값에 +1이 배열의 값이 된다.
• 규칙 2. 시작하는 위치 : i = left / n, j = left % n이 된다. 단, left < n일 경우 i = 0이 된다.
  !!!그런데 이런 규칙을 어떻게 찾냐? n이 3,4,5... 일 때를 그려보고 left, right를 임의로 설정해둔 다음 그냥,, 계속 관찰하는 수밖에 없는 듯..?
  필자는 n=5, left=23, right=24 일 때를 그려보고 찾았다.
  

23 / 5 = 4, 23 % 5 = 3 [4,3] 이 되는 기적..! 그럼 이제 풀어보자

3. 규칙을 찾았으니 반복문 1개로 어떻게 돌릴까 생각해야 한다. while문 안에서 i, j를 컨트롤 하는 방법이 낫겠다.

슈도코드

만약 left - n 이면 i = 0
아니면 i = left/n
j = left%n

while left가 right에 닿으면 종료
i,j 중 max 값 + 1
i,j++ 하지만 j가 다음 배열로 넘어가야 하기 때문에
j가 넘어가면 j=0, i++

풀이

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

    if left-n < 0:
        i = 0
    else:
        i = int(left/n)
    j = left % n

    while left != right+1:
        arr.append(max(i, j) + 1)
        left += 1

        if j == n-1:
            i += 1
            j = 0
        else:
            j += 1
            
    return arr