[프로그래머스] n^2 배열 자르기 - 파이썬

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

문제 설명

정수 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

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

입출력 예 #2

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

---

문제풀이

문제 이해하기:

목표: 정수 n, left, right가 매개변수로 주어질 때 주어진 과정대로 만들어진 1차원 배열을 return

내 풀이:

n 이 3일때랑 4일때 각 행별로 어떤 리스트가 만들어지는지 확인해봤다.

n = 3:

• [1, 2, 3]
• [2, 2, 3]
• [3, 3, 3]

n = 4:

• [1, 2, 3, 4]
• [2, 2, 3, 4]
• [3, 3, 3, 4]
• [4, 4, 4, 4]

규칙을 보면 각 행의 첫 번째 숫자가 각 행만큼 반복되고 나머지 숫자들은 순서대로 자리해 있는것을 확인할 수 있었다.

• 1행 [1, 2, 3]: 1 → 1개, 나머지 2, 3
• 2행 [2, 2, 3]: 2 → 2개, 나머지 3
• 3행 [3, 3, 3]: 3 → 3개, 나머지 X

첫 번째 풀이 코드:

def solution(n, left, right):
    answer = []
    for i in range(1, n+1):  # 각 행의 번호를 결정
        for j in range(i, n+1):  # 각 행의 숫자가 반복되는 부분을 결정
            if j == i:  # 첫 번째 숫자에 대해 해당 숫자만큼 반복하여 answer에 추가하기
                for k in range(j):  
                    answer.append(i)
            if j != i:  # 나머지 숫자들은 그대로 answer에 추가
                answer.append(j)
                
        
    return answer[left:right+1]  # left부터 right까지 return

• 하지만, 시간 초과로 실패.. 하긴 for 문이 3번이나 중첩돼서 시간복잡도가 $O(n^3)$ 이나 되니 그럴 수 있다.

두 번째 풀이:

그러면 이번에는 리스트를 모두 만들지 말고, 필요한 구간의 값만 계산해보자.

n = 3, left = 2, right = 5:

• arr = [[1, 2, 3], [2, 2, 3], [3, 3, 3]]
• left 와 right 를 각각 인덱스로 표현해보면
  • left: arr[0][2]
  • right: arr[1][2]

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

• arr = [[1, 2, 3, 4], [2, 2, 3, 4], [3, 3, 3, 4], [4, 4, 4, 4]]
• left 와 right 를 각각 인덱스로 표현해보면
  • left: arr[1][3]
  • right: arr[3][2]

규칙을 보면 arr[i][j] 에서 left 와 right 각각 n 으로 나눈 몫과 나머지가 i, j 가 되고 있었다.

• n=3, left=2 → 0, 2
• n=3, right=5 → 1, 2

그럼 이제 필요한 구간의 인덱스는 알아내어, 1차원 배열의 특정 인덱스에 해당하는 2차원 배열의 값을 구할 수 있게 됐다. 그러면 이제 구간에 대해 반복문을 돌면서 값을 리스트에 집어넣어야 하는데, 그 값은 어떻게 구할 수 있을까? 이 또한 예시를 통해 알아보자.

n = 3, left = 2, right = 5:

• arr = [[1, 2, 3], [2, 2, 3], [3, 3, 3]]
• left ~ right 까지 반복문을 돈다고 할 때 각 반복에서의 인덱스는:
  • 2: 0, 2 → 3이 돼야 함
  • 3: 1, 0 → 2가 돼야 함
  • 4: 1, 1 → 2가 돼야 함
  • 5: 1, 2 → 3이 돼야 함

잘 살펴보면 i 와 j 에 각각 1씩 더 해서 둘 중 더 큰 수가 해당 인덱스의 값이 되는 규칙성을 갖는것을 알 수 있다.

최종코드

def solution(n, left, right):
    answer = []
    
    # left ~ right까지 반복문을 돌면서 
    for i in range(left, right+1):
        row, col = divmod(i, n)  # i 를 n 으로 나눈 몫과 나머지를 각각 행과 열 변수에 저장하고
        answer.append(max(row+1, col+1))  # 행과 열에 1 씩 더한 값중 더 큰 수를 answer에 저장 
    
    return answer

• 이렇게 해서 시간 복잡도를 $O(n^3)$ 에서 $O(n)$ 까지 줄여 해결할 수 있었다.