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
입출력 예
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  3
2  2  3
3  3  3

->

1  2  3  2  2  3  3  3  3  3
      left     right

answer = [3, 2, 2, 3]

입출력 예 #2

1  2  3  4
2  2  3  4
3  3  3  4
4  4  4  4

->

1  2  3  4  2  2  3  4  3  3  3  4  4  4  4  4
                     left                 right

answer = [4, 3, 3, 3, 4, 4, 4, 4]

나의 풀이

def solution(n, left, right):
    answer = []
    numbers = dict()

    for i in range(left, right + 1):
        pos = i // n 
        remain = i % n

        if pos not in numbers.keys():
            arr = [0 for _ in range(n)]
            arr[0] = pos + 1
            for i in range(1, n):
                arr[i] = arr[0] if i + 1 <= arr[0] else i + 1
            numbers[pos] = arr
            
        answer.append(numbers[pos][remain])
        
    return answer
  • 최초에는 이중 for문을 활용하여 해당하는 경우의 숫자배열을 다 만들었다.
  • 하지만 이러한 형태는 n의 값이 조금만 늘어도 시간 초과가 발생한다.
  • 그렇기에 방법을 바꿔 left ~ right 까지의 범위를 어떻게 탐색하는 방식으로 변경함.
  • 더불어 최초에는 수학적인 계산으로 각 위치마다를 지정하려고 했지만, 패턴화 하기 쉽지 않아, 최초로 해당 줄을 만날 때만, 그 줄의 for문을 통해 배열 값들을 구해오는 구조를 떠올림
  • 가장 최적화가 잘된 것과 비교했을 때, 좀더 깊게 생각했다면 충분히 값을 도출 할 수 있었을 것이라는 생각이 듬.
케이스 결과
테스트 1 〉 통과 (28.49ms, 16MB)
테스트 2 〉 통과 (1694.30ms, 398MB)
테스트 3 〉 통과 (1694.51ms, 398MB)
테스트 4 〉 통과 (0.05ms, 10.2MB)
테스트 5 〉 통과 (0.04ms, 10.3MB)
테스트 6 〉 통과 (34.46ms, 15.8MB)
테스트 7 〉 통과 (38.71ms, 17.9MB)
테스트 8 〉 통과 (31.47ms, 17.5MB)
테스트 9 〉 통과 (40.11ms, 17.2MB)
테스트 10 〉 통과 (39.57ms, 18.7MB)
테스트 11 〉 통과 (37.94ms, 16.3MB)
테스트 12 〉 통과 (53.53ms, 17.2MB)
테스트 13 〉 통과 (56.36ms, 17.1MB)
테스트 14 〉 통과 (52.69ms, 15.8MB)
테스트 15 〉 통과 (175.30ms, 40.6MB)
테스트 16 〉 통과 (167.30ms, 42.5MB)
테스트 17 〉 통과 (168.00ms, 24.5MB)
테스트 18 〉 통과 (1454.97ms, 306MB)
테스트 19 〉 통과 (1650.14ms, 355MB)
테스트 20 〉 통과 (1216.04ms, 82MB)
## 다른 사람들의 풀이
```python
def solution(n, left, right): 
answer = []
for i in range(left,right+1):
    answer.append(max(i//n,i%n)+1)
return answer

|   |   |
|---|---|
|테스트 1 〉|통과 (21.71ms, 16.3MB)|
|테스트 2 〉|통과 (26.54ms, 18.9MB)|
|테스트 3 〉|통과 (25.81ms, 19.4MB)|
|테스트 4 〉|통과 (0.03ms, 10.2MB)|
|테스트 5 〉|통과 (0.02ms, 10.2MB)|
|테스트 6 〉|통과 (25.31ms, 18.3MB)|
|테스트 7 〉|통과 (26.57ms, 19MB)|
|테스트 8 〉|통과 (24.11ms, 17.7MB)|
|테스트 9 〉|통과 (26.76ms, 18.8MB)|
|테스트 10 〉|통과 (26.03ms, 18.6MB)|
|테스트 11 〉|통과 (25.64ms, 18.4MB)|
|테스트 12 〉|통과 (28.31ms, 18MB)|
|테스트 13 〉|통과 (32.18ms, 18.5MB)|
|테스트 14 〉|통과 (30.48ms, 18.3MB)|
|테스트 15 〉|통과 (29.40ms, 18.3MB)|
|테스트 16 〉|통과 (31.32ms, 18.3MB)|
|테스트 17 〉|통과 (32.00ms, 18.4MB)|
|테스트 18 〉|통과 (35.87ms, 19MB)|
|테스트 19 〉|통과 (32.21ms, 18.7MB)|
|테스트 20 〉|통과 (29.42ms, 18MB)|

```toc