[프로그래머스] 행렬과 연산
https://school.programmers.co.kr/learn/courses/30/lessons/118670
문제
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
당신은 행렬에 적용할 수 있는 두 가지 연산을 만들었습니다.
- ShiftRow
- 모든 행이 아래쪽으로 한 칸씩 밀려납니다. 즉, 모든 행에 대해서 i번째 행은 i+1번째 행이 됩니다. (마지막 행은 1번째 행이 됩니다.)
- ShiftRow의 예
- 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 ShiftRow를 한 번 시행한 뒤의 행렬입니다.
- 1번째 행에 있던 [1,2,3]이 2번째 행으로, 2번째 행에 있던 [4,5,6]이 3번째 행으로, 3번째 행에 있던 [7,8,9]가 1번째 행이 된 것을 확인할 수 있습니다.
- Rotate
- 행렬의 바깥쪽에 있는 원소들을 시계 방향으로 한 칸 회전시킵니다.
- 행렬의 바깥쪽에 있는 원소들은 첫 행, 첫 열, 끝 행, 끝 열에 포함되는 원소들입니다.
- 한 칸 회전시킨다는 것은 이 원소들이 시계 방향으로 한 칸씩 밀려난다는 것을 의미합니다. 즉, 다음 4개의 연산이 동시에 시행됩니다.
- 첫 행에서 끝 열에 있는 원소를 제외한 첫 행의 모든 원소는 오른쪽으로 한 칸 이동합니다.
- 끝 열에서 끝 행에 있는 원소를 제외한 끝 열의 모든 원소는 아래쪽으로 한 칸 이동합니다.
- 끝 행에서 첫 열에 있는 원소를 제외한 끝 행의 모든 원소는 왼쪽으로 한 칸 이동합니다.
- 첫 열에서 첫 행에 있는 원소를 제외한 첫 열의 모든 원소는 위쪽으로 한 칸 이동합니다.
- Rotate의 예
- 왼쪽 행렬이 초기 상태이고 오른쪽 행렬이 Rotate를 한 번 시행한 뒤의 행렬입니다.
- 바깥쪽에 있는 값들이 시계 방향으로 한 칸씩 이동한 것을 확인할 수 있습니다.
당신은 행렬에 연산을 여러 번 시행하려고 합니다.
행렬의 초기 상태를 담고 있는 2차원 정수 배열 rc, 시행할 연산을 순서대로 담고 있는 문자열 배열 operations가 매개변수로 주어졌을 때, 연산을 차례대로 시행한 후의 행렬 상태를 return 하도록 solution 함수를 완성해주세요.
제한사항
- 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 50,000
- rc의 모든 행의 길이는 동일합니다.
- 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 50,000
- rc의 모든 열의 길이는 동일합니다.
- 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 100,000
- rc[i][j] 는 i+1번째 행 j+1번째 열에 있는 원소를 나타냅니다.
- 1 ≤ rc[i][j] ≤ 1,000,000
- 1 ≤ operations의 길이 ≤ 100,000
- operations의 원소는 "ShiftRow" 혹은 "Rotate"입니다.
정확성 테스트 케이스 제한 사항
- 2 ≤ rc의 행 길이(=행렬의 가로 길이) ≤ 1,000
- rc의 모든 행의 길이는 동일합니다.
- 2 ≤ rc의 열 길이(=행렬의 세로 길이) ≤ 1,000
- rc의 모든 열의 길이는 동일합니다.
- 4 ≤ rc의 행 길이 x rc의 열 길이 ≤ 10,000
- 1 ≤ operations의 길이 ≤ 100
효율성 테스트 케이스 제한 사항
- 주어진 조건 외 추가 제한사항 없습니다.
해결방법
첫번째로 해본 방법은 단순 구현이었다. 문제 설명에 나와있는 방법대로 구현해보았는데 역시나 정확성 테스트는 다 맞았지만 효율성 테스트에서 시간초과가 나서 다른 방법을 찾아야했다.
그래도 구현하면서 리스트 복사의 얕은 복사, 깊은 복사를 배우게 되어서 코드를 기록해놓겠다.
단순히 lista=listb 식으로 코드를 짜면 같은 리스트에 이름 두개를 지정하는 것과 같기 때문에 lista를 변형할 경우 listb도 함께 변형되는 문제가 발생한다. 이런 문제를 방지하기 위하여 얕은 복사, 깊은 복사라는 개념이 나왔다.
얕은 복사는 lista=listb[:] 혹은 lista=listb.copy() 이렇게 구현하는건데, 이것은 listb를 수정할 때 lista 가 변하지 않지만, 둘은 다른 객체를 가르키고있지만 같은 요소를 가지고있다는 것이 나중에 문제가 될 수 있다. 따라서 깊은 복사를 사용했는데,
이를 사용하는 방법은
import copy
lista=copy.deepcopy(listb)
이렇게 사용한다고 한다. 이를 사용할 때 문제는 메모리를 많이 차지하게 되고, 처리시간도 오래걸리기 때문에 적절할 때 활용해야한다.
deepcopy를 처음 써보면서 구현한 첫번째 코드는 아래에 기재하겠다.
import copy
def solution(rc, operations):
answer = [[]]
answer=copy.deepcopy(rc)
def rotation(array1, array2) :
for x in range(len(array1)) :
for y in range(len(array1[0])) :
if x==0 :
if not y==len(array1[0])-1 :
array1[x][y+1]=array2[x][y]
if y==len(array1[0])-1 :
if not x==len(array1)-1 :
array1[x+1][y]=array2[x][y]
if x==len(array1)-1 :
if not y==0 :
array1[x][y-1]=array2[x][y]
if y==0 :
if not x==0 :
array1[x-1][y]=array2[x][y]
if y!=0 and y!=len(array1[0])-1 and x!=0 and x!=len(array1)-1:
array1[x][y]=array2[x][y]
return array1
def shift(array1, array2) :
for x in range(len(array1)):
for y in range(len(array1[0])) :
if x==len(array1)-1 :
array1[0][y]=array2[x][y]
else :
array1[x+1][y]=array2[x][y]
return array1
for oper in operations :
if oper=="Rotate" :
temp=rotation(answer, rc)
rc=copy.deepcopy(temp)
else :
temp=shift(answer, rc)
rc=copy.deepcopy(temp)
return rc
다시 보니 무식하게도 풀었다 ㅎ
다른 분의 코드를 참고하여 큐로 풀어나가야된다는 것을 알았다. 양 쪽 끝의 열에 있는 숫자들을 담을 큐를 out_cols에 담고,
양끝의 숫자를 제외한 중간 부분을 rows에 담은 후 popleft와 pop appendleft append 처리를 해주자. 시간 복잡도가 연산할 때 각각 O(1)이 걸리므로 효율성에서 시간초과가 뜨지않는다.
코드
from collections import deque
def solution(rc, operations):
answer = [[]]
q=deque(rc)
r_len=len(rc)
c_len=len(rc[0])
rows = deque(deque(row[1:-1]) for row in rc)
out_cols = [deque(rc[r][0] for r in range(r_len)),
deque(rc[r][c_len - 1] for r in range(r_len))]
def shift() :
rows.appendleft(rows.pop())
out_cols[0].appendleft(out_cols[0].pop())
out_cols[1].appendleft(out_cols[1].pop())
def rotation() :
#왼쪽 첫 열 이동
rows[0].appendleft(out_cols[0].popleft())
#위 첫 행에서 오른족 열로 이동
out_cols[1].appendleft(rows[0].pop())
#왼쪽 열에서 아래 맨 뒤 행 이동
rows[r_len-1].append(out_cols[1].pop())
#맨 아래 행에서 왼쪽 열로 이동
out_cols[0].append(rows[r_len-1].popleft())
for oper in operations :
if "S" in oper :
shift()
else :
rotation()
answer=[]
for r in range(r_len) :
temp=[]
temp.append(out_cols[0][r])
temp.extend(rows[r])
temp.append(out_cols[1][r])
answer.append(temp)
return answer