문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/87390
문제 설명
- 정수 n, left, right가 주어진다
- n행 n열 크기의 비어있는 2차원 배열을 만든다.
- 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i(1~n)로 채운다.
- 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만든다.
- 1차원 배열을 arr라고 할 때 arr[left:right+1]을 반환하라
1차 시도 - 시간초과 실패
def solution(n, left, right):
matrix = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
for j in range(n):
matrix[i][j] = max(i+1,j+1)
matrix = sum(matrix,[])
return matrix[left:right+1]n*n 행렬 전부 값을 구해서 1차원 배열로 flatten 하고 요구하는 리스트를 반환
행렬 값(요소)을 구하는 과정에서 max(행+1,열+1)이 해당 행,열의 원소 값이라는 걸 사용
시간초과로 인한 실패
but, 리스트 관련해서 배운 게 있다.
- 얕은 복사:
[[0]*n]*n과 같이 행렬을 만들면 얕은 복사가 일어나, 요소 변경시 다른 요소들도 함께 변경된다. 즉 arr[0][0]=2와 같이 변경하면 arr[x][0]도 2로 변경되는 문제가 발생한다. 이를 피하기 위해선[[0 for i in range(n)] for i in range(n)]과 같이 이차원 행렬을 선언해줘야한다. - 2차원 행렬 flatten: sum 함수는
sum(iterable, start)이기 때문에sum(arr,[])와 같이 작성시 이차원 배열인 arr가 1차원 배열로 변환된다.
2차 시도 - 시간 초과 실패
def solution(n, left, right):
matrix = []
for i in range(1,n+1):
matrix += [i]*i + list(range(i+1,n+1))
return matrix[left:right+1]이건 다른 규칙을 사용한건데, 그냥 눈에 보이는 규칙으로 코드를 작성해봤다.
예시로, n=4일 때 2(i)행이면 [2,2,3,4]길래 각 행을 [i]*i + list(range(i+1,n+1))로 구성해보았다.
근데 얘도 시간 초과실패
- range to list :
list(range(i,j))와 같이 변환
3차 시도 - 통과
matrix = []
for i in range(left//n, right//n+1):
for j in range(0,n):
if i==right//n and j==right%n+1:
break
matrix.append(max(i,j))
matrix = [i+1 for i in matrix]
return matrix[left%n:]대갈빡 돌리다가 안돌아가서 ... 근데 어쨌든 계속 시간 초과 나는걸로 보아 행렬을 모두 구하면 안되는 것 같아서 일부만 구하기 시작.
어쩌다가 left와 right의 몫과 나머지를 구해보니 행렬의 인덱스임을 알아냄.
그래서 left의 행과 right의 행까지만 for문을 돌고, 열은 모두 돌아서 범위 축소해냄.
그러고 나머지 이용해서 원하는 부분만 슬라이싱.
드디어 통과 !!!!!!!!!! 어쨌든,,, 다른 풀이 안보고 통과는 했다..
근데??????
left, right와 같은 flatten list의 인덱스의 몫과 나머지가 행렬의 인덱스인 걸 알아냈고, max(행,열)로 값을 하나하나 구하고있으면서 왜 그냥 range(left, right+1)의 값들의 몫과 나머지를 행과 열로 이용해서 요소 값을 구할 생각은 못했지...
암튼 그래서 다른 사람 풀이 보고 생각한게 아래 4차 시도다.
4차 시도 - 개간단!
return [max(i//n,i%n)+1 for i in range(left, right+1)]한줄 ...
ㅎㅎ
내가 너무 복잡하게 생각한건가?
이렇게까지 오래 걸릴 문제는 아니었던 것 같은데, 약간 힘빠지지만 배운게 많다. 시야를 확장하자~
정리
- 얕은 복사:
[[0]*n]*n과 같이 행렬을 만들면 얕은 복사가 일어나, 요소 변경시 다른 요소들도 함께 변경된다. 즉 arr[0][0]=2와 같이 변경하면 arr[x][0]도 2로 변경되는 문제가 발생한다. 이를 피하기 위해선[[0 for i in range(n)] for i in range(n)]과 같이 이차원 행렬을 선언해줘야한다. - 2차원 행렬 flatten: sum 함수는
sum(iterable, start)이기 때문에sum(arr,[])와 같이 작성시 이차원 배열인 arr가 1차원 배열로 변환된다. - range to list :
list(range(i,j))와 같이 변환 - n*n 행렬의 flatten index을 n으로 나눈 몫과 나머지가 행,열 인덱스다.
