문제
이번에 풀 문제는 행렬 테두리 회전하기이다.
풀이 과정
이 문제를 보고 처음 생각했던 건 그냥 나온대로 풀자! 였다.
근데 테두리를 어떻게 돌 수 있을 지 고민하느라 좀 헤맸다.
상하좌우마다 따로 for문으로 돌까 생각도 했지만 코드가 더러워질 거 같아서
하나의 로직으로 할 수 없을까 고민하다가 아래처럼 구현했다.
풀이시간은 한시간 정도 걸린 것 같다. 줄여야 하는데..
- 처음 위치부터 시작해서 다시 처음위치로 올 때 까지 아래를 반복한다.
- 현재 탐색 방향(direction)을 토대로 다음 위치를 구한다.
- 다음 위치가 탐색해야할 범위를 벗어나면 탐색 방향을 적절하게 바꿔준다.
- 탐색중에 최솟값을 발견하면 계속 업데이트 해준다.
- 1-4에서 구한 마지막 최솟값을 answer에 추가해준다.
최종 코드
def solution(rows, columns, queries):
answer = []
m = [[i * columns + (j + 1) for j in range(columns)] for i in range(rows)]
for query in queries:
# 탐색해야할 사각형에서 왼쪽 위(시작) 좌표
start_row = query[0] - 1
start_col = query[1] - 1
# 탐색해야할 사각형에서 오른쪽 아래 좌표
end_row = query[2] - 1
end_col = query[3] - 1
# 오른쪽, 아래, 왼쪽, 위 순서로 탐색해야하니까
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
# 시작위치를 r,c(현재 탐색할 좌표)에 넣어줌
r = start_row
c = start_col
# 어느 방향으로 진행할 지
# 예를들어 0 이면 (dr[0], dc[0]) = (0,1) 즉 오른쪽 방향으로 하나씩 늘려가는 방향이라는 뜻
direction = 0
# 현재 위치에 넣어줄 숫자
# 처음에는 시작 숫자를 넣어줘야 하니까 초기화
curr_num = m[start_row][start_col]
# 최솟값
min_num = 1e9
while True:
# 다음 좌표
nr = r + dr[direction]
nc = c + dc[direction]
# 다음 좌표가 탐색 범위를 벗어나면
if not start_row <= nr <= end_row or not start_col <= nc <= end_col:
# direction이 3(위로)인데 다음위치가 범위를 벗어났다면
# 사각형 테두리 탐색을 완료해서 다시 처음으로 돌아왔다는 뜻이니까 끝냄
if direction == 3:
break
# 탐색 방향 변경
direction += 1
continue
next_num = m[nr][nc]
# 다음 위치에 현재 숫자를 넣음
m[nr][nc] = curr_num
# 다음 위치에 있는 숫자를 또 그 다음 위치에 넣어 줘야 하기 때문에 업데이트 해줌
curr_num = next_num
# 다음 위치를 현재 위치로 좌표 업데이트
r, c = nr, nc
# 최솟값 찾기
if curr_num < min_num:
min_num = curr_num
# 최솟값을 답에 추가
answer.append(min_num)
return answer
주석 제거 코드
def solution(rows, columns, queries):
answer = []
m = [[i * columns + (j + 1) for j in range(columns)] for i in range(rows)]
for query in queries:
start_row = query[0] - 1
start_col = query[1] - 1
end_row = query[2] - 1
end_col = query[3] - 1
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
r = start_row
c = start_col
direction = 0
curr_num = m[start_row][start_col]
min_num = 1e9
while True:
nr = r + dr[direction]
nc = c + dc[direction]
if not start_row <= nr <= end_row or not start_col <= nc <= end_col:
if direction == 3:
break
direction += 1
continue
next_num = m[nr][nc]
m[nr][nc] = curr_num
curr_num = next_num
r, c = nr, nc
if curr_num < min_num:
min_num = curr_num
answer.append(min_num)
return answer
결과는 통과!
다른 사람의 풀이
import sys
def solution(rows, columns, queries):
arr = [[(i)*columns+(j+1) for j in range(columns)] for i in range(rows)]
result = []
for x1, y1, x2, y2 in queries:
result.append(change(x1-1, y1-1, x2-1, y2-1, arr))
return result
def change(x1, y1, x2, y2, arr):
min_value = sys.maxsize
# 맨 위의 맨 왼쪽 값을 기록
temp = arr[x1][y1]
# 왼쪽
for k in range(x1, x2):
arr[k][y1] = arr[k+1][y1]
min_value = min(min_value, arr[k+1][y1])
# 아래
for k in range(y1, y2):
arr[x2][k] = arr[x2][k+1]
min_value = min(min_value, arr[x2][k+1])
# 오른쪽
for k in range(x2, x1, -1):
arr[k][y2] = arr[k-1][y2]
min_value = min(min_value, arr[k-1][y2])
# 위
for k in range(y2, y1+1, -1):
arr[x1][k] = arr[x1][k-1]
min_value = min(min_value, arr[x1][k-1])
# 기록했던 값 업데이트
arr[x1][y1+1] = temp
min_value = min(min_value, temp)
return min_value의외로 대부분의 사람들이 상하좌우를 따로 구현하고 있었다..!
코드도 의외로 깔끔하다.
개발자