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

1. 전체 코드

def solution(n, left, right):
    left_complete = left // n
    right_complete = right // n

    # left 와 right 가 같은 행에 존재
    if left_complete == right_complete:
        # arr[start: end + 1]
        start = left % n
        end = right % n
        left_main_num = left_complete + 1
        arr = [left_main_num] * left_main_num
        for i in range(left_main_num + 1, n + 1):
            arr.append(i)
        return arr[start: end + 1]

    # left
    rest = left % n
    left_main_num = left_complete + 1
    left_in_list = [left_main_num] * left_main_num
    for i in range(left_main_num + 1, n + 1):
        left_in_list.append(i)
    left_result = left_in_list[rest:]

    # right
    rest = right % n
    right_main_num = right_complete + 1
    right_in_list = [right_main_num] * right_main_num
    for i in range(right_main_num + 1, n + 1):
        right_in_list.append(i)
    right_result = right_in_list[:rest + 1]

    # mid
    mid = []
    for i in range(left_main_num + 1, right_main_num):
        for _ in range(i):
            mid.append(i)
        for j in range(i + 1, n + 1):
            mid.append(j)

    answer = left_result + mid + right_result
    return answer

2. 후기

# 2중 for 문
graph = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        # 대각
        if i == j:
            graph[i][j] = i + 1
        # 대각 제외 나머지
        elif graph[i][j] == 0:
            graph[i][j] = j + 1
            graph[j][i] = j + 1

문제에서 주어진 n의 최대 범위가 2000 전후였다면, 위의 코드처럼 O(n^2)인 알고리즘을 구현하여 문제를 풀어도 문제가 없었을 것이다. 하지만 n의 최대 값은 10,000,000으로 매우 크기 때문에 2중 for문은 사용할 수 없다.

따라서 배열의 모든 값을 구현하는게 아니라 문제에서 요구하는 left와 right의 범위만큼의 값만 배열로 만들어야 한다. 또한 조건 right - left < 100,000이 주어졌으므로, 최대 범위는100,000으로 잡고 알고리즘을 설계해야 한다.

3. 풀이

3-1. left와 right가 다른 행에 있는 경우

# n =4, left = 7, right = 14

[1, 2, 3, 4]
[2, 2, 3, 4(left)]
[3, 3, 3, 4] (mid)
...
[4, 4, 4(right), 4]

left_result = [4]
mid = [3, 3, 3, 4]
right_result = [4, 4, 4]

answer = [4, 3, 3, 3, 4, 4, 4, 4]

1. left_complete와 right_complete는 각각 처음 행부터 left와 right가 속한 행의 바로 전 행까지 완료된 행의 갯수이다. 위의 예시에서는 각각 1, 3이다.

2. rest는 left와 right가 그 행에서 몇 번째 인덱스인지 저장한다. 위의 예시에서는 각각 3, 2이다.

3. append는 행의 길이가 n이 될 때 까지 반복하며 i 값을 추가한다. right도 동일하게 수행한다.

    left_main_num = left_complete + 1
    left_in_list = [left_main_num] * left_main_num
    for i in range(left_main_num + 1, n + 1):
        left_in_list.append(i)
        
 # [2, 2] : 초기화 
 # [2, 2, 3] : for문 i = 3, append(3)
 # [2, 2, 3, 4]: for문 n = i = 4, append(4)

4. left는 부터, right는 까지 이므로 슬라이싱의 범위를 다르게 해야 한다.

     left_result = left_in_list[rest:]
     right_result = right_in_list[:rest + 1]

5. left가 속한 행의 다음 행부터 right가 속한 행의 바로 전 행까지의 값을 저장하는 mid를 구한다. 행을 구성하는 방식은 위와 동일하다.

    mid = []
    for i in range(left_main_num + 1, right_main_num):
        for _ in range(i):
            mid.append(i)
        for j in range(i + 1, n + 1):
            mid.append(j)            

6. answer에 모두 더해준다.

    answer = left_result + mid + right_result

3.2 left와 right가 같은 행에 있는 경우

1. 따로 left, right, mid를 구현 할 필요가 없고 하나의 배열만 필요하기 때문에 바로 답을 return 하는 조건문을 추가했다.

2. 행을 구성하는 알고리즘은 3.1과 같고, start와 end가 rest이다.