정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.
진짜 문제에서 시키는 대로 한 풀이. n의 범위를, 그리고 left, right의 범위를 보면 절대 문제에서 시키는 대로 하면 안 된다는 것을 알 수 있다. 공간도 엄청 많이 쓰고 시간초과도 나기 때문.
def solution(n, left, right):
board = [[0] * n for _ in range(n)]
for i in range(n):
for col in range(n):
board[i][col] = i+1
for row in range(n):
board[row][i] = i+1
arr = []
for i in range(n):
arr = arr + board[i]
return arr[left:right+1]
만약에 n이 4라고 할 때, 2차원 배열을 각각의 행으로 끊어본다면 다음과 같이 된다.
즉, k(k >= 1)번째 행에서는 k가 k번 나오고, 나머지 (n-k)번 만큼은 k에서 하나씩 증가하는 수로 채워진다.
이러한 규칙을 이용해서, 어떤 인덱스를 넘겼을 때, 그게 몇 번째 행인지 알아내서 [3, 3, 3, 4]와 같은 행 한 줄을 뱉어내는 함수(makeRow
)를 만든다. 이게 핵심아이디어이다.
start, end가 주어졌을 때, n으로 나눈 몫을 행번호로 구한 다음
를 나눠서 생각한 다음, 각 행마다 반복문을 돌려서 다음과 같은 로직을 수행한다.
def solution(n, left, right):
arr = []
def makeRow(no):
ret = [(no+1)] * (no+1)
for i in range(n - no - 1):
ret.append(no+1+i+1)
return ret
start = left // n
end = right // n
if start == end:
temp = makeRow(start)
return temp[left%n:right%n+1]
for index in range(start, end+1):
if index == start:
arr += makeRow(start)[left%n:]
elif index == end:
arr += makeRow(end)[:right%n+1]
else:
arr += makeRow(index)
return arr
그것보다 더 대박인 것은...
어떤 인덱스(i
)가 주어졌을 때, 우리가 구하는 수는 max(i//n
, i%n
)+1 이라는 것이었다.
def solution(n, left, right):
answer = []
for i in range(left,right+1):
answer.append(max(i//n,i%n)+1)
return answer