행렬과 연산
접근 방법 [필수 작성]
제한 조건 확인
단순 구현문제로 보이지만... 시간 복잡도가..?
가로세로길이의 합이 최대가 될 수 있는 값 -> root(100,000) -> root(2^10100) -> root(2^17) -> 2^9 -> 512
-> 가로 또는 세로 최대 길이는 어림 512 -> 512^2 -> 26만
로테이트 최대 연산수 -> 4 512 -> 2,000
→ 잘못된 생각임
로우시프트 최대 연산수 -> 50000
오퍼레이션 길이 최대 100,000
20만 x 10만 -> 5,000,000,000 -> 50억?
로우시프트 오퍼레이션 때문에
리스트로 구현하면 안되고,
queue로 구현해야 될 것 같다...
큐로 구현하면 rotate 가 복잡하다.
-> 근데 어차피 로테이트 할때도
양끝에서 변화가 일어나기 때문에 구현가능
아이디어
데큐를 이용한 단순구현
로우시프트 함수
이중 데큐에서 오른쪽끝 데큐를 뽑아서 왼쪽 끝에 배치
로테이트 함수
첫번째 줄의 오른쪽 끝 원소를 뽑아서 tmp_before 에 저장
i번째줄의 왼쪽끝 뽑아서 i-1번째 왼쪽끝에 append
i번째줄의 오른쪽 끝 뽑아서 tmp_after에 저장
i번째줄의 오른쪽 끝에 tmp_before 를 저장
tmp_after 를 tmp_before 에 저장
마지막 직전줄까지 위 사항 반복
마지막줄이라면
i번째줄의 왼쪽끝 뽑아서 i-1번째 왼쪽끝에 append
i번째줄의 오른쪽 끝에 tmp_before 를 저장
시간복잡도
데큐를 이용하면 통과가능으로 예상
자료구조
코드 구현 [필수 작성]
1차 시도 (45분 소요)
효율성 테스트 → 1,2,4,6 번 테케 시간초과
시간초과??? 왜 때문에???
시간초과가 날만한 곳은
deque ↔ list 로 전환하는 작업
또는
for문
전환작업의 시간복잡도는
전체 원소의 갯수만큼이다
최대 원소갯수는 보수적으로 어림잡아 26만 이기때문에 여기서 시간초과가 나는것은 아니라고 유추할 수 있다.
→ 최대 원소갯수는 10만개
shift_row 는 O(1) 만에 끝나지만
rotate 는 최대 row_num 만큼의 반복을한다. → row_num은 최대 5만
operation이 rotate 만 있을경우 operation 최대 10만이기 때문에
→ 5,000,000,000 → 50억 → 데큐로 구현해도 의미가 없다.
그럼 생각할 수 있는 방법은
rotate를 연속해서 x 번 해서 제자리로 돌아오는 경우 제거
→ 근본적인 해결책이 되지 못한다.
근본적으로 이 문제를 해결하려면 rotate 함수 또한 O(1) 의 시간복잡도로 끝낼 수 있어야한다. O(n) 의 경우 n 은 가로 길이 가 최대 5만이 될 수 있기 때문에 이렇게 구현하면 탈락이다.
그럼 생각할 수 있는 방법은
가장 껍질부분을 deque 로 다시 구현해서 껍질부분만 돌리는 방법이다.
근데 좌우 양끝 껍질부분만 새로운 deque 로 만드는 거 자체가 O(n) 의 시간복잡도를 가진다… 애초에 만들때 잘 만들면 되지 않을까?
from collections import deque
def solution(rcs, operations):
answer = []
deque_rcs = deque([])
for rc in rcs:
deque_rcs.append(deque(rc))
def shift_row(deque):
deque.appendleft(deque.pop())
def rotate(deque):
tmp_before = 0
tmp_after = 0
row_num = len(deque)
tmp_before = deque[0].pop() # 첫번째 줄의 오른쪽 끝 원소를 뽑아서 tmp_before 에 저장
for i in range(1,row_num-1): #마지막 전줄까지
deque[i-1].appendleft(deque[i].popleft()) # i번째줄의 왼쪽끝 뽑아서 i-1번째 왼쪽끝에 append
tmp_after = deque[i].pop() # i번째줄의 오른쪽 끝 뽑아서 tmp_after에 저장
deque[i].append(tmp_before) # i번째줄의 오른쪽 끝에 tmp_before 를 저장
tmp_before = tmp_after # tmp_after 를 tmp_before 에 저장
# 마지막줄이라면
deque[row_num-2].appendleft(deque[row_num-1].popleft())# 마지막번째줄의 왼쪽끝 뽑아서 i-1번째 왼쪽끝에 append
deque[row_num-1].append(tmp_before)# i번째줄의 오른쪽 끝에 tmp_before 를 저장
for operation in operations:
if operation == "ShiftRow":
shift_row(deque_rcs)
elif operation == "Rotate":
rotate(deque_rcs)
for deque_rc in deque_rcs:
answer.append(list(deque_rc))
return answer2차 시도
이러한 형식으로 큐를 만들면 되지 않을까?
→ 통과!!!! 캬!!!!
from collections import deque
def solution(rc, operations):
len_r = len(rc)
len_c = len(rc[0])
left = deque([])
right = deque([])
center = deque([])
for r in range(len_r):
tmp_center = deque([])
for c in range(len_c):
if c == 0:
left.append(rc[r][c])
elif c == len_c-1:
right.append(rc[r][c])
else:
tmp_center.append(rc[r][c])
center.append(tmp_center)
def shift_row(left,right,center):
left.appendleft(left.pop())
right.appendleft(right.pop())
center.appendleft(center.pop())
def rotate(left,right,center):
# left 의 첫번째 원소를 빼서 center의 0번째 sub row 의 왼쪽 끝에 추가
center[0].appendleft(left.popleft())
# center 의 0번째 sub row 의 오른쪽 끝을 빼서, right 의 왼쪽에 추가
right.appendleft(center[0].pop())
# right 의 오른쪽 끝 원소를 빼서 center 의 마지막번째 sub row 의 오른쪽에 추가
center[len_r-1].append(right.pop())
# center 의 마지막번째 sub row 의 왼쪽원소를 빼서 left 의 오른쪽 끝에 추가
left.append(center[len_r-1].popleft())
for operation in operations:
if operation == "ShiftRow":
shift_row(left,right,center)
elif operation == "Rotate":
rotate(left,right,center)
# print(left)
# print(center)
# print(right)
for r in range(len_r):
for c in range(len_c):
if c == 0:
rc[r][c] = left[r]
elif c == len_c - 1:
rc[r][c] = right[r]
else:
#print(r,c)
rc[r][c] = center[r][c-1]
return rc
배우게 된 점 [ 필수 X ]
자유 형식
질문 [ 필수 X ]
자유 형식
피드백 [ 코치 작성 ]
자유 형식
