사용 언어: python 3.9.5
❓ Problem
문제 설명
https://programmers.co.kr/learn/courses/30/lessons/77485
난이도
level 2
🚩 Solution
시도 01)
⚠ 시간초과
정답 : 시도 02)
1. 접근법
-
전처리 : 왼쪽변과 위쪽변에 0을 채운 2차원 배열을 만든다.
-
쿼리 이전에 arr의 상태를 temp에 저장한다. (value 복사, deepcopy 사용)
→ 전체 말고 쿼리에 필요한 부분한 복사할 수 있는 방법이 있다면 시간을 더 절약할 수 있을 것 같다...
-
회전 : temp에서 바로 이전 값들을 가져와서 arr에 대입한다.
num은 최솟값을 항상 유지하게 min()을 사용한다.
-
변경된 arr의 상태를 temp에 다시 복사하며 쿼리를 반복한다.
2. 코드
import copy
def solution(rows, columns, queries):
# 전처리 : 왼쪽변과 위쪽변에 0을 채운 2차원 배열
arr = []
temp = []
i=1
for r in range(rows+1):
for c in range(columns+1):
if r == 0 or c == 0:
temp.append(0)
else:
temp.append(i)
i += 1
arr.append(temp)
temp = []
num = 100000 # 최솟값
answer = []
for q in queries:
x1, y1 = q[0], q[1]
x2, y2 = q[2], q[3]
# 쿼리 이전에 arr의 상태를 temp에 저장
temp = copy.deepcopy(arr)
# 회전 : temp에서 바로 이전 값들을 가져와서 arr에 대입
for i in range(x1, x2+1): #i : 현재 행의 위치
for j in range(y1, y2+1): #j : 현재 열의 위치
if x1 <= i and i < x2 and j == y1: # 왼쪽변
arr[i][j] = temp[i+1][j]
num = min(num, arr[i][j])
elif i == x1 and y1 < j and j <= y2: # 윗변
arr[i][j] = temp[i][j-1]
num = min(num, arr[i][j])
elif x1 < i and i <= x2 and j == y2: # 오른쪽변
arr[i][j] = temp[i-1][j]
num = min(num, arr[i][j])
elif i == x2 and y1 <= j and j < y2: # 아랫변
arr[i][j] = temp[i][j+1]
num = min(num, arr[i][j])
answer.append(num)
num = 100000
return answer
근데 deepcopy()를 사용하여 시간초과
시도 02)
1. 접근법
접근 방법은 똑같음
검색해보니까 deepcopy()가 슬라이싱보다 오래걸린다고 함
그래서 deepcopy() 라인을 슬라이싱으로 바꾸니까 통과함
2. 코드
import copy
def solution(rows, columns, queries):
# 전처리 : 왼쪽변과 위쪽변에 0을 채운 2차원 배열
arr = []
temp = []
i=1
for r in range(rows+1):
for c in range(columns+1):
if r == 0 or c == 0:
temp.append(0)
else:
temp.append(i)
i += 1
arr.append(temp)
temp = []
num = 100000 # 최솟값
answer = []
for q in queries:
x1, y1 = q[0], q[1]
x2, y2 = q[2], q[3]
# 쿼리 이전에 arr의 상태를 temp에 저장
temp = [item[:] for item in arr] # 슬라이싱
# temp = copy.deepcopy(arr)
# 회전 : temp에서 바로 이전 값들을 가져와서 arr에 대입
for i in range(x1, x2+1): #i : 현재 행의 위치
for j in range(y1, y2+1): #j : 현재 열의 위치
if x1 <= i and i < x2 and j == y1: # 왼쪽변
arr[i][j] = temp[i+1][j]
num = min(num, arr[i][j])
elif i == x1 and y1 < j and j <= y2: # 윗변
arr[i][j] = temp[i][j-1]
num = min(num, arr[i][j])
elif x1 < i and i <= x2 and j == y2: # 오른쪽변
arr[i][j] = temp[i-1][j]
num = min(num, arr[i][j])
elif i == x2 and y1 <= j and j < y2: # 아랫변
arr[i][j] = temp[i][j+1]
num = min(num, arr[i][j])
answer.append(num)
num = 100000
return answer3. 시간복잡도
4. 결과
성공
5. 소요 시간
1시간 이상...
📕 피드백
1. 검색한 내용
2차원 배열 value 복사하는 법(주소참조x)
슬라이싱이 더 빠르니까 슬라이싱을 사용하도록 하자!
- 슬라이싱
temp = [item[:] for item in arr]- copy의 deepcopy() 사용
import copy
temp = copy.deepcopy(arr)2. 실수
제출할 때 print 그대로 내서 출력 초과 떴음.
print는 꼭 주석으로 바꾸거나 지우고 제출하자
1차원 처럼 2차원 배열 value 복사도 arr[:]만 하면 복사되는 줄 알고 코드 짜다가 오래걸렸다...
3. 발전 방향 (개선/추가사항)
2차원 배열의 일부분만 추출하는 방법에 대해서도 공부하자
https://programming119.tistory.com/169
4. 다른 사람 풀이
풀이1)
- 링크
https://minnit-develop.tistory.com/23
- 접근법
array[x1-1][y1] 빼고 회전시킴(왼쪽 세로 -> 하단 가로 -> 오른쪽 세로 -> 상단 가로 순)
tmp = array[x1-1][y1-1]를 통해 미리 값을 저장해뒀다가 회전끝나고 다시 대입해줌 array[x1-1][y1] = tmp
- 코드
def solution(rows, columns, queries):
answer = []
array = [[0 for col in range(columns)] for row in range(rows)]
t = 1
for row in range(rows):
for col in range(columns):
array[row][col] = t
t += 1
for x1,y1,x2,y2 in queries:
tmp = array[x1-1][y1-1]
mini = tmp
for k in range(x1-1,x2-1):
test = array[k+1][y1-1]
array[k][y1-1] = test
mini = min(mini, test)
for k in range(y1-1,y2-1):
test = array[x2-1][k+1]
array[x2-1][k] = test
mini = min(mini, test)
for k in range(x2-1,x1-1,-1):
test = array[k-1][y2-1]
array[k][y2-1] = test
mini = min(mini, test)
for k in range(y2-1,y1-1,-1):
test = array[x1-1][k-1]
array[x1-1][k] = test
mini = min(mini, test)
array[x1-1][y1] = tmp
answer.append(mini)
return answer- 배울 점
전체를 복사해둘 필요 없이 하나만 복사하는 방법.
처음 잘못된 1개를 나중에 다시 올바르게 고침
처음부터 다 올바르게 동작하지 않고 나중에 고쳐도 된다
