행렬 테두리 회전하기 (Python)
0. 출처
1. 기록
2. 풀이
(1) 아이디어, 시간복잡도, 자료구조
1. 아이디어
>> queries에서 값을 graph에서 잘 위치시키도록 한다.
>> 왼쪽 끝은 오른쪽으로 이동 등
>> 총 4섹터로 나눌 수 있음
>> x1,y1,x2,y2 라는 변수로 이용할 것임
>> rows colums 로
>> 1, 2, 3, 4, ... 의 순서대로 garph 를 만들어줘야 함.
2. 시간복잡도
3. 자료구조
>> 이차원 배열 이용
(2-1) 시간초과 풀이
import copy
def start(rows, columns, graph1, graph2):
for r in range(rows):
graph1.append([a for a in range(r*columns+1, (r+1)*columns+1)])
graph2.append([a for a in range(r*columns+1, (r+1)*columns+1)])
def solution(rows, columns, queries):
graph1 = []
graph2 = []
answer = []
start(rows, columns, graph1, graph2)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
while queries:
min_value = 10000
x1, y1, x2, y2 = queries.pop(0)
x1 = x1 - 1
y1 = y1 - 1
x2 = x2 - 1
y2 = y2 - 1
for i in range(rows):
for j in range(columns):
if i == x1 and y1<=j<y2:
# 우로 이동
nx = i + dx[0]
ny = j + dy[0]
graph2[nx][ny] = graph1[i][j]
min_value = min(min_value ,graph1[i][j])
elif j == y2 and x1<=i<x2:
# 아래로 이동
nx = i + dx[1]
ny = j + dy[1]
graph2[nx][ny] = graph1[i][j]
min_value = min(min_value ,graph1[i][j])
elif i == x2 and y1<j<=y2:
# 좌로이동
nx = i + dx[2]
ny = j + dy[2]
graph2[nx][ny] = graph1[i][j]
min_value = min(min_value ,graph1[i][j])
elif j == y1 and x1<i<=x2:
# 위로 이동
nx = i + dx[3]
ny = j + dy[3]
graph2[nx][ny] = graph1[i][j]
min_value = min(min_value ,graph1[i][j])
else:
continue
answer.append(min_value)
graph1 = copy.deepcopy(graph2) # 깊은 복사해야 내가 의도한 대로 된다.
if queries == []:
print(answer)
return answer
(2-2) 다시 풀이
def solution(rows, columns, queries):
answer = []
table = []
for r in range(rows):
table.append([a for a in range(r*columns+1, (r+1)*columns+1)])
for query in queries:
query = [x-1 for x in query] # 0부터 시작하는 인덱스에 맞춰 1씩 빼줌
tmp = table[query[0]][query[1]] # 왼쪽 위 값 저장
small = tmp
# left
for i in range(query[0]+1, query[2]+1):
table[i-1][query[1]] = table[i][query[1]]
small = min(small, table[i][query[1]])
# bottom
for i in range(query[1]+1, query[3]+1):
table[query[2]][i-1] = table[query[2]][i]
small = min(small, table[query[2]][i])
# right
for i in range(query[2]-1, query[0]-1, -1):
table[i+1][query[3]] = table[i][query[3]]
small = min(small, table[i][query[3]])
# top
for i in range(query[3]-1, query[1]-1, -1):
table[query[0]][i+1] = table[query[0]][i]
small = min(small, table[query[0]][i])
table[query[0]][query[1]+1] = tmp
answer.append(small)
return answer
(3) 참고 및 정리
# 내가 실수한 부분, 이렇게 0을 삽입해 놓은 이차원 배열을 만들어버리면 append 할 때 배열이 추가적으로 더 생기게 됨.
# graph1 = [[0]*columns for _ in range(rows)]
# graph2 = [[0]*columns for _ in range(rows)]
# 이렇게 빈 배열을 만든 뒤에 append 하면 된다.
graph1 = []
graph2 = []
# 내가 못만든 부분, 1부터 순서대로 어떻게 집어넣지 한참 생각함
for r in range(rows):
graph1.append([a for a in range(r*columns+1, (r+1)*columns+1)])
graph2.append([a for a in range(r*columns+1, (r+1)*columns+1)])
graph1 = copy.deepcopy(graph2) # 깊은 복사해야 내가 의도한 대로 된다. 얕은 복사하면 의도대로 안됨.
처음 풀이처럼 한 이유는 회전시 이동하는 값이 다음 위치의 값을 차지함으로서 값을 덮어버리는 문제가 있습니다.
그래서 graph1 에서 회전한 결과를 graph2 에 만들어놓고 완성된 graph2 를 다시 graph1 에 깊은 복사하는 형식으로 해결하였으나 시간초과가 발생하였습니다.
시간초과한 풀이로 하는 경우 graph1, graph2 등 이차원 배열 2개를 사용해서 시간초과가 나는 것 같습니다.
참고한 풀이 처럼 graph 한개만을 이용해서 해결해야 하는 듯 합니다.
'참고한 풀이1'에서는 for문을 4개로 나누어 시계방향 역순으로 값들을 회전시켰으며 마지막에 처음에 x1,y1 에 해당하는 값을 기억하여 이동시켜줌으로서 이러한 문제를 해결하였습니다.
참고한 풀이1