[파이썬] 백준 16926 배열 돌리기 1, 16927 배열 돌리기 2

[배열돌리기 2]

 

문제링크 https://www.acmicpc.net/problem/169267

 

배열돌리기 1을 할 때는 원본 배열을 copy해서 돌렸는데 한번 돌릴때마다 계속 배열을 복사해야 하다보니 시간이 오래걸렸다.

배열돌리기 2에서도 배열돌리기 1에서 하던 로직으로 pypy3는 통과했지만, python에서는 시간초과가 났다.

그래서, queue를 사용해서 1차원적으로 접근해 돌릴 수 있는 만큼 다 돌리고 원본배열에 반영했는데 훨씬 쉬웠다. queue같은 경우 linkedlist로 구현돼 맨앞이나 맨뒤에서 append나 pop이 일어난다고 해도 O(1)안에 연산이 가능해 시간도 많이 줄었다. python으로도 268ms에 맞았습니다 판정이 났다.

 

 

[배운점]

while과 queue의 조합이 너무 좋았다!

 

from collections import deque

N, M, R = map(int, input().split())  # N*M 배열을 반시계로 R번 돌림
arr = [list(map(int, input().split())) for _ in range(N)]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]

def rotate():
    q = deque()
    for depth in range(min(N, M) // 2):
        r = c = depth

        for dr, dc in move:  # 큐에 담아놓고
            while True:
                nr = r + dr
                nc = c + dc
                if depth <= nr < N - depth and depth <= nc < M - depth:
                    q.append(arr[r][c])
                    r = nr
                    c = nc
                else:
                    break

        # 돌린다
        for _ in range(R % ((N - depth * 2) * 2 + (M - depth * 2) * 2 - 4)):
            q.appendleft(q.pop())

        for dr, dc in move: #큐에서 돌린 값을 넣는다
            while True:
                nr = r + dr
                nc = c + dc
                if depth <= nr < N - depth and depth <= nc < M - depth:
                    arr[r][c]=q.popleft()
                    r = nr
                    c = nc
                else:
                    break

# 큐에서 값을 빼 저장한다
rotate()

for i in range(N):
    for j in range(M):
        print(arr[i][j], end=" ")
    print()

 

 

 

 

 

 

 

 

 

 

[배열돌리기 1]

문제링크 https://www.acmicpc.net/problem/16926

 

[배운점]

1. deepcopy<리스트 슬라이싱 (리스트 슬라이싱으로 복사하는게 더 빠르다)

2. 더 이상 갈 곳이 없으면 방향 돌리기 

 

 

[답코드]

N, M, R = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 하우상좌


def rotate():
    carr = [[] for _ in range(N)]

    for i in range(N):#배열 복사
        carr[i]=arr[i][:]

    sr = 0; sc = 0; er = N - 1; ec = M - 1
    for depth in range(min(M, N)//2):
        r = sr
        c = sc
        for d in move:
            while True:
                nr = r + d[0]
                nc = c + d[1]
                if sr <= nr <= er and sc <= nc <= ec:
                    arr[nr][nc] = carr[r][c]
                    r = nr
                    c = nc
                else:
                    break
        sr+=1; sc+=1; er-=1; ec-=1


for r in range(R):  # 전체 회전 횟수
    rotate()

for i in range(N):
    print(*arr[i])

 

for문 방향별로 4개 돌릴 때 머리쓰느라 고통스러웠는데 while로 처리하는게 훨씬 간편했다!