https://www.acmicpc.net/problem/16926
16926번: 배열 돌리기 1
크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5]
www.acmicpc.net
배열 돌리기 1
| 1 초 | 512 MB | 12089 | 5794 | 3833 | 46.721% |
문제
크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.
A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
↓ ↑
A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5]
↓ ↓ ↑ ↑
A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5]
↓ ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.
1 2 3 4 2 3 4 8 3 4 8 6
5 6 7 8 1 7 7 6 2 7 8 2
9 8 7 6 → 5 6 8 2 → 1 7 6 3
5 4 3 2 9 5 4 3 5 9 5 4
<시작> <회전1> <회전2>배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.
입력
첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.
둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.
출력
입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.
풀이 (시간초과)
import sys
input = sys.stdin.readline
import copy
n, m, r = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
turned_graph = [[0]*m for _ in range(n)]
for _ in range(r):
for i in range(n//2):
tmp = i
for j in range(tmp, m):
if j == m-tmp:
continue
# 왼쪽 방향
nx, ny = i+dx[2], j+dy[2]
if 0<= nx < n and 0+tmp<= ny < m:
turned_graph[nx][ny] = graph[i][j]
for i in range(n-1, n//2-1, -1):
tmp = n-i-1
for j in range(tmp, m):
if j == m-tmp:
continue
# 오른쪽 방향
nx, ny = i + dx[3], j + dy[3]
if 0<= nx < n and 0<= ny < m:
turned_graph[nx][ny] = graph[i][j]
for i in range(m//2):
tmp = i
for j in range(tmp, n):
if j == n-tmp:
continue
# 아래 방향
nx, ny = j + dx[1], i + dy[1]
if 0+tmp <= nx < n-tmp and 0 <= ny < m:
turned_graph[nx][ny] = graph[j][i]
for i in range(m-1, m//2-1, -1):
tmp = m-i-1
for j in range(tmp, n):
if j == n-tmp:
continue
# 윗 방향
nx, ny = j + dx[0], i + dy[0]
if 0+tmp <= nx < n-tmp and 0 <= ny < m:
turned_graph[nx][ny] = graph[j][i]
graph = copy.deepcopy(turned_graph)
for i in turned_graph:
print(*i)이차원 배열로 두고 풀었는데, 시간초과가 났다.
이 코드를 짜는데도 디버깅 하는 부분에서 오랜 시간이 걸렸다.
첫 번째 둘레와 두 번째 둘레가 독립적으로 회전하는 규칙이 있는데, 이걸 2차원 리스트로 한꺼번에 돌리려 하니
for문을 사용할 때 인덱싱 부분 처리에서 매우 복잡했다.
그래서 인덱싱 오류가 많았고 이를 하나하나 고치는데 많은 시간이 걸렸다. ㅠ
풀이 (참고한 풀이) 2차원 리스트를 1차원 배열로 바꿔서 풀어주기
[Python] 백준 16926번: 배열 돌리기 1
백준 16926번: 배열 돌리기 1 문제 풀이에 대한 기록입니다.
velog.io
아이디어는 다음과 같다.
왼쪽 상단 원소를 껍질의 시작점이라 가정하고, 시작 상태 배열에서의 각 껍질을 시계방향으로 순서대로 나열하면 다음과 같아진다.
첫 번째 껍질 : 1 2 3 4 8 6 2 3 4 5 9 5
두 번째 껍질 : 6 7 7 8
이 상태에서 회전시키는 것은 아주아주 쉽다.
맨 앞에서부터 R개의 원소를 잘라 맨 뒤에 붙여주기만 하면 된다.
첫 번째 껍질 2번 회전 후 : 3 4 8 6 2 3 4 5 9 5 1 2
두 번째 껍질 2번 회전 후 : 7 8 6 7
이 문제는 각 테두리가 독립적으로 움직이는 원리를 이용해서 푸는 문제였다.
따라서 무식하게 for문으로 꾸역꾸역 구현하는게 아니라 문제의 의도를 파악하고 원리를 최대한 이용해서 풀어야 한다.😂
먼저, deque관련 함수 몇개 공부
1. rotate()
# Contain 1, 2, 3, 4, 5 in deq
deq = deque([1, 2, 3, 4, 5])
deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])
deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])2. clear()
모든 원소를 지운다.
3. extend()
리스트 전체를 삽입할때 사용한다.
전체 풀이 코드
from sys import stdin
from collections import deque
N, M, R = map(int, stdin.readline().split())
matrix = []
answer = [[0]*M for _ in range(N)]
deq = deque()
for i in range(N):
matrix.append(list(stdin.readline().split()))
# 각 껍질별로 나누어 작업하기 위해서 배열의 행과 열인 N, M 중 짝수인 쪽의 절반(껍질의 개수가 됨) 만큼 for문을 반복시킨다.
loops = min(N, M) // 2
for i in range(loops):
deq.clear()
deq.extend(matrix[i][i:M-i])
deq.extend([row[M-i-1] for row in matrix[i+1:N-i-1]])
deq.extend(matrix[N-i-1][i:M-i][::-1])
deq.extend([row[i] for row in matrix[i+1:N-i-1]][::-1])
deq.rotate(-R)
for j in range(i, M-i): # 위쪽
answer[i][j] = deq.popleft()
for j in range(i+1, N-i-1): # 오른쪽
answer[j][M-i-1] = deq.popleft()
for j in range(M-i-1, i-1, -1): # 아래쪽
answer[N-i-1][j] = deq.popleft()
for j in range(N-i-2, i, -1): # 왼쪽
answer[j][i] = deq.popleft()
for line in answer:
print(" ".join(line))
코드 복습하고 ✔️
혼자 다시 짜보기