프로그래머스 - 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

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

입출력 예 #2

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

---

내 코드

def solution(n, left, right):
    return [max(i//n,i%n)+1 for i in range(left,right+1)]

아이디어

🔍 첫번째 삽질

입출력 예시 gif에 속아 넘어가서 일일이 2차원 배열에 접근해서 행,열 중 큰값+1을 수행해서 배열에 assign 후, left-right만큼 slice 하는 로직으로 구현했었지만!

def solution(n, left, right):
    answer = [[0]*n for _ in range(n)]
    arr = [] # 새로운 1차원 배열
    
    for i in range(len(answer)):
        for j in range(n):
            k = max(i,j) # 행,열 중 큰값을 골라 +1 
            answer[i][j] = k+1
            arr.append(answer[i][j])
            
    arr = arr[left:right+1]
    return arr

시간초과 에러 발생 ^^.. (제발 제한사항을 보고 .... )
애초에 2차원 배열에 할당하는 사이즈 n값이 $10^7$ 범위까지 입력 받기 때문에 시간초과 에러가 발생했다.

🔓 해결

이 문제는 n값 보다는 우리가 slice할 left,right와 그리고 n과의 상관관계를 따져봤어야 할 문제다.

그래서 위와 같이 그 규칙성을 따져 본 결과,

1. 2차원 배열의 행과 열은 i//n ,i%n 이라는 수식으로 구할 수 있음
2. 그리고 그 중에서 max값+1 이 실제 2차원 배열에 할당된 값과 동일

위 2가지를 고려하여 구현하면 정답이다... 제한사항을 잘 읽는 습관을 들이자