[Python - Lv.2] n^2 배열 자르기

문제

프로그래머스

문제

입출력 예 (1)

입출력 예 (2)

문제 이해

• 정수 n, left, right가 입력으로 주어짐
• 문제의 1 ~ 4의 방법으로 생성된 1차원 배열을 찾아야 함
• 직관적인 이해를 위해 위의 입출력 예 (1), (2) 참고

풀이 1

문제에서 요구하는 방식으로 1차원 배열을 생성하여 arr[left:right+1]을 반환
n의 크기가 최대 10^7이므로 시간 복잡도를 고려해야 되는 문제일 수도 있음

1. 문제에서 제시된 방식으로 1차원 배열 생성
2. arr[left:right+1] 반환

<1차원 배열 생성>
반복문으로 n번 반복하면서 i를 i개 append, n까지 1씩 증가시키며 append를 반복
n = 1
1
=> 1

n = 2
1 2
2 2
=> 1 2 2 2

n = 5
1 2 3 4 5
2 2 3 4 5
3 3 3 4 5
4 4 4 4 5
5 5 5 5 5
=> 1 2 3 4 5 2 2 3 4 5 3 3 3 4 5 4 4 4 4 5 5 5 5 5 5

코드

예상대로 시간 초과로 문제를 틀렸다! 1차원 배열의 완성 후에 반환을 하려고 해서 그런가 하고, len(arr) >= right 조건도 넣었지만 마찬가지로 시간 초과였다. 이후 풀이 2를 생각하여 코드를 보완하였다.

# 풀이 1 - 시간 초과
def solution(n, left, right):
    arr = []
    for i in range(1, n + 1):
        for j in range(i):
            arr.append(i)
        for j in range(i + 1, n + 1):
            arr.append(j)
        if len(arr) >= right:
            return arr[left:right + 1]
# return arr[left:right + 1]

풀이 1 - 시간 초과

풀이 2

불필요한 부분을 구하지 않고, left:right+1 부분만 찾도록 작성

1. 1차원으로 변경했을 때 left와 right를 포함하는 2차원 배열의 행을 각각 탐색
2. left와 right를 포함하는 1차원 배열을 풀이 1의 방식으로 구함
3. 문제에서 요구하는 arr[left:right+1]을 반환 (단, 여기서는 중간 행부터 탐색하므로 적절한 인덱스를 참조)

코드

가독성을 위해 start_row, end_row, start, end 변수를 선언해주었고, 변수 없이 바로 대입해주어도 무방하다. 

# 풀이 2 - 해결
def solution(n, left, right):
    arr = []
    
    start_row = left // n + 1
    end_row = right // n + 1
    for i in range(start_row, end_row + 1):
        for j in range(i):
            arr.append(i)
        for j in range(i + 1, n + 1):
            arr.append(j)
    
    start = left % n
    end = start + (right - left)
    return arr[start:end + 1]

풀이 2 - 해결