87. n^2 배열 자르기

[문제]

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

 

[풀이] 정확성문제]

 

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

 

 

 

[풀이] 정확성

1. 1부터 n 까지 i 를 뽑아 행을 하나씩 만들어가는데 i 행의 경우 i 로 i 번까지 채우고 그 다음부터 1씩 늘려서 채워야함

2. while 문과 for 문으로 이를 구현하고 만들어진 배열에 left와 right로 인덱싱해서 반환한다

3. 시간복잡도 n^2 으로 오답처리된다.

def solution(n, left, right):
    answer = []
    for i in range(1, n+1):
        k = i
        while k > 0:
            k -= 1
            answer.append(i)
        for j in range(i+1, n+1):
            answer.append(j)

    return answer[left:right+1]

 

[풀이] 효율성

n = 5일 때, 배열을 1차원으로 펼쳐보자.

[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]

 

이를 5개씩 끊고 인덱스와 함께 살펴보자

1, 2, 3, 4, 5 / 2, 2, 3, 4, 5 /   3,  3,  3,  4,  5 

 

0, 1, 2, 3, 4 / 5, 6, 7, 8, 9 / 10, 11, 12, 13, 14

 

그러면 어떤 규칙을 찾을 수 있는데 각 파트마다 몫으로 구분되고 그 안의 요소는 나머지로 구분된다는 것이다.

즉, 인덱스로 해당 배열에 접근할 때 인덱스를 n으로 나눈 몫과 나머지로 해당 배열의 요소가 결정된다는 것이다.

 

기본적으로 요소는 (나머지 + 1)로 결정되고, 몫에 따라 요소의 최소값이 결정된다

left와 right를 사이를 돌면서 각 인덱스별로 요소를 계산해 리턴한다.

def solution(n, left, right):
      answer = []
      for position in range(left, right+1):
         x, y = divmod(position, n)
         answer.append(max((y + 1), (x + 1)))
      return answer