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

목차

• 문제 설명

• 제한 사항

• 입출력 예

• 풀이과정

• 정답

문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.

2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   • 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.

3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.

4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ n ≤ $10^7$

• 0 ≤ left ≤ right < $n^2$

• right - left < $10^5$

입출력 예

n	left	right	result
3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

풀이과정

1. 첫 번째 풀이 (시간 초과 발생)
   • n행 n열 배열 (2차원 배열) 을 생성하고 각 배열에 값 설정
   • 2차원 배열을 1차원 배열로 변환
   • 1차원 배열을 슬라이싱하여 리턴

   def solution(n, left, right):
       answer = []
       
       arr = [[0 for _ in range(n)] for _ in range(n)]
       for i in range(n):
           for j in range(i):
               arr[i][j] = i+1
           for j in range(i, n):
               arr[i][j] = j+1
       
       for row in arr:
           answer += row
           
       return answer[left:right+1]

   ⇒ 이렇게 풀면 2중 포문에 의해 시간복잡도가 O($n^2$)로, 시간 초과가 발생한다.

2. 두 번째 풀이 (시간 초과 발생)
   • n*n열 배열 (1차원 배열) 을 생성하고 각 배열에 값 설정
   • 1차원 배열을 슬라이싱하여 리턴

   def solution(n, left, right):
       answer = [0 for _ in range(n*n)]
               
       for i in range(n):
           for j in range(i):
               answer[i*n+j] = i+1
           for j in range(i, n):
               answer[i*n+j] = j+1
       
       return answer[left:right+1]

   ⇒ 메모리 재할당&복사 과정은 생략되었지만 역시나 시간 초과 발생 → 여전히 시간 복잡도 O($n^2$)

3. 세 번째 풀이 (정답)
   • left와 right까지의 과정만 계산

   def solution(n, left, right):
       answer = [0 for _ in range(right-left+1)]
       
       for k in range(right-left+1):
           i, j = (k+left)//n, (k+left)%n
           if i <= j:
               answer[k] = j + 1
           else:
               answer[k] = i + 1
   
       return answer

   ⇒ 시간 복잡도 O(right-left+1) = O(n)로 최적화

정답

def solution(n, left, right):
    answer = [0 for _ in range(right-left+1)]
    
    for k in range(right-left+1):
        i, j = (k+left)//n, (k+left)%n
        if i <= j:
            answer[k] = j + 1
        else:
            answer[k] = i + 1

    return answer