Matrix 문제 1. 행렬 Transposed
Matrix 문제 1. 행렬 Transposed — #LeetCode #개발자의도구들 #코딩테스트Matrix문제 #행렬Transposed only 파이썬 목표 참고 : 여기 onl...
#LeetCode#Naver Blog
#LeetCode #개발자의도구들 #코딩테스트Matrix문제 #행렬Transposed
- only 파이썬
- 목표 참고 : 여기
LeetCode(medium 48. Rotate Image) 77.3%
⚠️ n x n (1 .. 20)
⚠️ in-place
🤔 어렵다 ...
>>> 찾은 규칙 들
✅ 내부 사각형 규칙
>>> n - 2 -> n - 2 - 2개씩 0이 될때까지 들어잇다.
✅ 테두리에 따라 idx의 특징
>>> 가장자리 ➡️ 0 or last idx
>>> 한 칸 씩 안으로 ➡️ 0 + 1 or last idx - 1
🤔 찾은 규칙을 바탕으로 문제를 풀어보자.
✅ 한 줄 씩 차례대로 넣어보자
✅ 임시 저장소로 queue를 사용하자.
only rotate logic
from collections import deque
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n = len(matrix[0])
que = deque()
# top -> right
for i in range(n):
right = matrix[i][n - 1]
que.append(right)
matrix[i][n - 1] = matrix[0][i]
# right -> bottom
for i in range(n):
bottom = matrix[n - 1][i]
que.append(bottom)
matrix[n - 1][i] = que.pop()
# bottom -> left
for i in range(n):
left = matrix[i][0]
que.append(left)
matrix[i][0] = que.leftpop()
# left -> top
for i in range(n):
matrix[0][i] = que.pop()
- 일단은 항상 겉면을 회전시키는 로직만 구현했다.
- 이제 내부도 확인해야한다
- 내부는 점차 적으로 1씩 감소 시키면 된다.
- ✅ while 문을 사용하면 될 것 같다.
- 변수가 아닌 곳을 변수로 치환해야한다.
테두리를 감소시키기
🤔 n갑을 줄여나가는 전략?
>>> n값을 줄여나가기 보다는 k값을 둬서 중간까지 이동하도록 구현하였다.
✅ pivot = n // 2로 둔다
✅ n이 홀수든 짝수든 k는 pivot전까지 이동한다.
✅ n값을 직접 줄이는 것보다 각 for문에서 k에 영향을 받도록 한다.
>>> 테두리는 k만큼 각각 감소한다.
>>> i는 변경할 필요가 없다.
from collections import deque
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n = len(matrix[0])
k = 0
pivot = n // 2
while k < pivot:
r_que = deque()
b_que = deque()
l_que = deque()
# top -> right
for i in range(k, n - k):
right = matrix[i][n - 1 - k]
r_que.append(right)
matrix[i][n - 1 - k] = matrix[0 - k][i]
print("after right updated: r_que", r_que)
print("matrix", matrix)
# right -> bottom
for i in range(k, n - k):
bottom = matrix[n - 1 - k][i]
b_que.append(bottom)
matrix[i][n - 1 - k] = r_que.pop()
print("after bottom updated: b_que", b_que)
# bottom -> left
for i in range(k, n - k):
left = matrix[i][0 + k]
l_que.append(left)
matrix[i][0 + k] = b_que.popleft()
print("after left updated: l_que", l_que)
# left -> top
for i in range(k, n - k):
matrix[0 + k][i] = l_que.pop()
k += 1
- top -> right에서 bottom값을 저장하는 곳에서 오류가 났다.
- bottom 값을 전부 복사하기 전에 matrix를 변경해버리기 때문이었다.
- 복사 로직과 swap로직을 분리하는게 좋겠다.
copy & swap 로직 분리하기
from collections import deque
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n = len(matrix[0])
k = 0
pivot = n // 2
while k < pivot:
t_que = deque()
r_que = deque()
b_que = deque()
l_que = deque()
# top copy
for i in range(k, n - k):
top = matrix[0 - k][i] ➡️ 행 + -> 0 + k가 되어야 한다.
t_que.append(top)
# right copy
for i in range(k, n - k):
right = matrix[i][n - 1 - k]
r_que.append(right)
# bottom copy
for i in range(k, n - k):
bottom = matrix[n - 1 - k][i]
b_que.append(bottom)
# left copy
for i in range(k, n - k):
left = matrix[i][0 + k]
l_que.append(left)
print("t_que: {}\nr_que: {}\nb_que {}\nl_que {}\n".format(t_que, r_que, b_que, l_que))
# top -> right
for i in range(k, n - k):
print("updated {}, {}".format(i, n-1-k))
matrix[i][n - 1 - k] = t_que.popleft()
# right -> bottom
for i in range(k, n - k):
matrix[i][n - 1 - k] = r_que.pop() ➡️ 현재 로직은 right를 업데이트한다.
➡️ bottom 업데이트로 변경해야 한다.
# bottom -> left
for i in range(k, n - k):
matrix[i][0 + k] = b_que.popleft()
# left -> top
for i in range(k, n - k):
matrix[0 + k][i] = l_que.pop()
k += 1
- 거의 다 되는데 디테일 부분에서 자꾸 실패한다.
input : [[1,2,3],[4,5,6],[7,8,9]]
❌ output: [[7,4,1],[8,5,6],[9,8,3]]
expected : [[7,4,1],[8,5,2],[9,6,3]]
- print 찍어보니 bottom 부분 로직을 이상하게 처리했다.
최종코드
from collections import deque
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n = len(matrix[0])
k = 0
pivot = n // 2
while k < pivot:
t_que = deque()
r_que = deque()
b_que = deque()
l_que = deque()
# top copy
for i in range(k, n - k):
top = matrix[0 + k][i]
t_que.append(top)
# right copy
for i in range(k, n - k):
right = matrix[i][n - 1 - k]
r_que.append(right)
# bottom copy
for i in range(k, n - k):
bottom = matrix[n - 1 - k][i]
b_que.append(bottom)
# left copy
for i in range(k, n - k):
left = matrix[i][0 + k]
l_que.append(left)
print("t_que: {}\nr_que: {}\nb_que {}\nl_que {}\n".format(t_que, r_que, b_que, l_que))
# top -> right
for i in range(k, n - k):
print("updated {}, {}".format(i, n-1-k))
matrix[i][n - 1 - k] = t_que.popleft()
print("right updated: ", matrix)
# right -> bottom
for i in range(k, n - k):
matrix[n - 1 - k][i] = r_que.pop()
print("bottom updated: ", matrix)
# bottom -> left
for i in range(k, n - k):
matrix[i][0 + k] = b_que.popleft()
print("left updated: ", matrix)
# left -> top
for i in range(k, n - k):
matrix[0 + k][i] = l_que.pop()
print("top updated: ", matrix)
k += 1
- t: O(n²) Beats 12.46%
- k = pivot = n / 2
- \*
- copy & swap = n
- s: O(n)
⚠️ 같은 코드를 지속적으로 submit하면 갑자기 Beat율이 100%로 변경되다 ..
코드르 줄여보자
행렬의 Transpose를 활용하기
🫡 transpose를 사용하면 간단하게 해결이 가능하다.
>>> transpose는 행렬의 주 대각 성분을 제외한 나머지 원소들을 뒤집는다.
✅ 1. transpose
✅ 2. reverse each rows
from collections import deque
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n = len(matrix[0])
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(n):
matrix[i].reverse()
- 이렇게 행렬의 성질을 알면 간단하게 해결이 가능하다.
- matrix문제에서 행렬도 고려해보자.