프로그래머스 - 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 ≤ 107
• 0 ≤ left ≤ right < n2
• right - left < 105

---

입출력 예nleftrightresult

3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

---

입출력 예 설명

입출력 예 #1

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

입출력 예 #2

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

 

나의 풀이

def solution(n, left, right):
    answer = []
    for i in range(left+1, right+2):
        if i%n == 0:
            answer.append(n)
        elif i%n < i//n + 1:
            answer.append(i//n + 1)
        else:
            answer.append(i%n)
            
    return answer

*처음 문제를 보고 이중 리스트로 접근해서 슬라이싱을 생각했지만 이중 포문을 돌리는 시간 복잡도 N**2이 시간 초과가 떴다. 그래서 규칙성을 찾고 O(n)으로 풀어야했다.

 

1) 조건에 맞는 left와 right까지의 값만 추출하기 위해 반복문 돌린다.

1-1) +1, +2를 해준 것은 몇 번째 수인지에 따라 나머지 값을 구하기 위해 저렇게 접근함.

1-2) 해당 수의 몇번째인지 나머지가 0일 때는 n을 대입

1-3) 나머지가 몫에 1을 더한 값보다 작은 값에는 몫에 1을 더한 값을 대입

1-4) 위 조건에 해당 안되면 그냥 나머지를 대입!