배열 돌리기 1 (백준 16926번)
문제
크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.
1
2
3
4
5
6
7
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
5
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번 회전시킨 결과를 출력한다.
제한
- 2 ≤ N, M ≤ 300
- 1 ≤ R ≤ 1,000
- min(N, M) mod 2 = 0
나의 풀이 (시간초과)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import sys
input=sys.stdin.readline
N,M,R=map(int,input().strip().split())
array=[]
for _ in range(N):
a=list(map(int,input().strip().split()))
array.append(a)
if N<M: #N이 짝수
odd_n=N
even_n=M
else:
odd_n=M
even_n=N
for _ in range(R):
min_r=0
min_c=0
max_r=N-1
max_c=M-1
for i in range(odd_n//2): #총 N/2만큼의 배열 수
a_num=(max_r-min_r+max_c-min_c)*2 #총 element수
c_r=min_r
c_c=min_c
tmp=array[c_r][c_c]
for j in range(a_num):
if c_c==min_c and c_r!=max_r:
tmp2=array[c_r+1][c_c]
array[c_r+1][c_c]=tmp
c_r+=1
tmp=tmp2
elif c_r==max_r and c_c!=max_c:
tmp2=array[c_r][c_c+1]
array[c_r][c_c+1]=tmp
c_c+=1
tmp=tmp2
elif c_c==max_c and c_r!=min_r:
tmp2=array[c_r-1][c_c]
array[c_r-1][c_c]=tmp
c_r-=1
tmp=tmp2
elif c_r==min_r and c_c!=min_c:
tmp2=array[c_r][c_c-1]
array[c_r][c_c-1]=tmp
c_c-=1
tmp=tmp2
min_r+=1
min_c+=1
max_r-=1
max_c-=1
for i in range(N):
print(*array[i])
- 규칙을 찾아 총 회전하는 배열의 수를 찾고, min과 max값을 설정하여, 경계선을 따라 수가 1씩 증가하도록 만들었다.
- 각 값을 임시로 저장해놓고, 순차적으로 다음 순서에 배치에 하는 코드를 작성하였는데 시간 초과가 발생하여서 deque()를 이용하여 아래와 같이 수정했다.
나의 풀이 (정답)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import sys
from collections import deque,defaultdict
input=sys.stdin.readline
N,M,R=map(int,input().strip().split())
array=[]
for _ in range(N):
a=list(map(int,input().strip().split()))
array.append(a)
if N<M: #N이 짝수
odd_n=N
even_n=M
else:
odd_n=M
even_n=N
array_dict=defaultdict(deque)
min_r=0
min_c=0
max_r=N-1
max_c=M-1
for i in range(odd_n//2): #총 N/2만큼의 배열 수
a_num=(max_r-min_r+max_c-min_c)*2 #총 element수
c_r=min_r
c_c=min_c
for j in range(a_num):
if c_c==min_c and c_r!=max_r:
array_dict[i].append(array[c_r][c_c])
c_r+=1
elif c_r==max_r and c_c!=max_c:
array_dict[i].append(array[c_r][c_c])
c_c+=1
elif c_c==max_c and c_r!=min_r:
array_dict[i].append(array[c_r][c_c])
c_r-=1
elif c_r==min_r and c_c!=min_c:
array_dict[i].append(array[c_r][c_c])
c_c-=1
min_r+=1
min_c+=1
max_r-=1
max_c-=1
for i in range(odd_n//2):
for _ in range(R):
array_dict[i].appendleft(array_dict[i].pop())
min_r=0
min_c=0
max_r=N-1
max_c=M-1
for i in range(odd_n//2): #총 N/2만큼의 배열 수
a_num=(max_r-min_r+max_c-min_c)*2 #총 element수
c_r=min_r
c_c=min_c
for j in range(a_num):
if c_c==min_c and c_r!=max_r:
array[c_r][c_c]=array_dict[i].popleft()
c_r+=1
elif c_r==max_r and c_c!=max_c:
array[c_r][c_c]=array_dict[i].popleft()
c_c+=1
elif c_c==max_c and c_r!=min_r:
array[c_r][c_c]=array_dict[i].popleft()
c_r-=1
elif c_r==min_r and c_c!=min_c:
array[c_r][c_c]=array_dict[i].popleft()
c_c-=1
min_r+=1
min_c+=1
max_r-=1
max_c-=1
for i in range(N):
print(*array[i])
- 각 배열의 값들을 먼저 저장한 후, 회전 수에 따라 deque의 pop, append를 이용하면 시간초과 없이 문제를 해결할 수 있다.
This post is licensed under CC BY 4.0 by the author.