[백준 16926번] 배열 돌리기 1 (python/파이썬)

문제 설명을 그대로 구현했더니 시간초과가 떠서, 좀더 효율적인 방법을 고안해야 했음.

 

🌼 문제 링크

https://www.acmicpc.net/problem/16926

16926번: 배열 돌리기 1

• 티어: 실버 I
• 분류: 구현

 

 

❗ TRIAL 1.

코드

def move(v1, v2, direction, arr, ans):
    if direction == 'l':
        x = v1[0]
        for y in range(v1[1], v2[1]):
            ans[x][y] = arr[x][y+1]
    elif direction == 'u':
        y = v1[1]
        for x in range(v1[0], v2[0]):
            ans[x][y] = arr[x+1][y]
    elif direction == 'r':
        x = v1[0]
        for y in range(v2[1]+1, v1[1]+1):
            ans[x][y] = arr[x][y-1]
    else: # 'd'
        y = v1[1]
        for x in range(v2[0]+1, v1[0]+1):
            ans[x][y] = arr[x-1][y]
    return ans
    
N, M, R = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

ans = [[0 for _ in range(M)] for _ in range(N)]

num_circle = min(N//2, M//2)
for r in range(R):
    for i in range(num_circle):
        v = [(i, i), (i, M-i-1), (N-i-1, M-i-1), (N-i-1, i), (i, i)]
        d = ['l', 'u', 'r', 'd']
        for j in range(4):
            ans = move(v[j], v[j+1], d[j], arr, ans)
    arr = [ans_i[:] for ans_i in ans]

for ans_i in ans:
    print(' '.join(map(str, ans_i)))

 

코드 설명

 

- 같은 회전 group 안에 있는 원소 단위로 회전을 회전 횟수만큼 진행함.

- 각 회전에 대해, l, u, r, d로 방향을 지정하고 배열을 회전시킴.

 

틀린 원인

 

시간초과. 각 원소들이 회전하므로, 일정 횟수의 회전 이후에는 원래 상태와 동일하게 되는데 이를 고려하지 않았음.

 

 

❗ TRIAL 2.

코드

def move(v1, v2, direction, arr, ans):
    if direction == 'l':
        x = v1[0]
        for y in range(v1[1], v2[1]):
            ans[x][y] = arr[x][y+1]
    elif direction == 'u':
        y = v1[1]
        for x in range(v1[0], v2[0]):
            ans[x][y] = arr[x+1][y]
    elif direction == 'r':
        x = v1[0]
        for y in range(v2[1]+1, v1[1]+1):
            ans[x][y] = arr[x][y-1]
    else: # 'd'
        y = v1[1]
        for x in range(v2[0]+1, v1[0]+1):
            ans[x][y] = arr[x-1][y]
    return ans

N, M, R = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

ans = [arr_i[:] for arr_i in arr]

num_circle = min(N//2, M//2)
for i in range(num_circle):
    R_i = R%(2*(M+N-4*i-2))
    for _ in range(R_i):
        v = [(i, i), (i, M-i-1), (N-i-1, M-i-1), (N-i-1, i), (i, i)]
        d = ['l', 'u', 'r', 'd']
        for j in range(4):
            ans = move(v[j], v[j+1], d[j], arr, ans)
        arr = [ans_i[:] for ans_i in ans]

for ans_i in ans:
    print(' '.join(map(str, ans_i)))

 

수정한 부분

 

- 각 회전에 대해서, 회전 횟수를 회전하는 원소의 갯수로 나눈 나머지 만큼만 회전시켜서 회전 횟수를 최소한으로 했음.

 

틀린 원인

 

시간초과. 문제에서 설명한 방식처럼 매 회전마다 한 번의 for 문을 돌게 하면 iteration 횟수가 너무 늘어나기 때문에 다른 방식으로 회전을 구현해야 함.

 

💡 Solution

코드

N, M, R = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
arrT = [list(x) for x in zip(*arr)]

num_circle = min(N//2, M//2) #함께 회전하는 group의 개수

for i in range(num_circle):
    c_h, c_w = N-2*i-1, M-2*i-1
    R_i = R%(2*(c_h+c_w)) #최소 회전 횟수
    
    circle_line = arr[i][i:i+c_w] + arrT[i+c_w][i:i+c_h] + arr[i+c_h][i+c_w:i:-1] + arrT[i][i+c_h:i:-1]
    
    new_circle_line = circle_line[R_i:] + circle_line[:R_i]
    
    arr[i][i:i+c_w] = new_circle_line[:c_w] #u
    arr[i+c_h][i+1:i+c_w+1] = new_circle_line[2*c_w+c_h-1:c_w+c_h-1:-1] #d
    for dx in range(c_h): 
        arr[i+dx][i+c_w] = new_circle_line[c_w+dx] #r
        arr[i+c_h-dx][i] = new_circle_line[2*c_w+c_h+dx] #l

for ans_i in arr:
    print(' '.join(map(str, ans_i)))

 

코드 설명

• 같은 회전 group 안에 있는 원소 단위로 한 번에 회전을 진행함
• 회전 횟수를 회전하는 원소의 갯수로 나누어 최소 회전 횟수를 구함
• 우선, 같은 회전 group 안에 있는 원소들을 일렬로 펼쳐서 하나의 list에 모두 담음 (circle_line). 이를 for 문 없이 구현하기 위해 arr를 transpose한 arrT를 처음에 저장함.
• circle_line을 자르고 순서를 바꾸는 방식으로 회전을 구현
• 이를 다시 arr에 순서대로 담음.

 

주의사항

• 문제에서 설명한 바와 같이 회전 횟수만큼 회전을 구현하면, (혹은 최소 회전 횟수만큼만 구현해도) 시간초과가 뜸.

 

다른 풀이

• 풀이1: queue와 while문을 이용
  • i번째 회전 group의 시작점은 (i, i)이고, 각 회전 group의 크기는 (N, M)부터 시작해서 2씩 줄어든다.
  • 각 회전 group에 대해 우->하->좌->상 순서로 queue에 append한다.
  • -R만큼 rotate한다.
  • 회전한 queue를 순서대로 pop하여 다시 배열에 대입한다.
  • 내 풀이와의 차이점: queue를 사용한다는 것을 제외하면 전체적인 로직은 내 코드와 비슷하나, 훨씬 깔끔하고 직관적이다.시간복잡도는 비슷할듯.. 특히 while 문을 이용해서 각 회전 group의 시작점과 h, w를 지정하고, 매 iteration마다 +1/-2를 해줌으로써 값을 변경해서 깔끔하게 구현할 수 있었다.