[백준] 16926번 파이썬 - 배열 돌리기 1

백준 16926

 

첫번째 풀이

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

사실 문제 제한이 다음과 같아서 풀면서도 아.. 시간 초과 날 것 같은데 라는 생각을 하긴 했다.

내 풀이대로라면 r * min(n,m) // 2 * (각 for문에서 돌아가는 while 문의 수) 만큼 계산하는데

대충 계산해보아도 시간 제한 1초가 넘어가게 생겼다.

진작 풀이 갈아엎을껄..

혹시나 해서 짰는데 역시나 시간초과 문제가 생겼다.

 

n,m,r = map(int,input().split())
array = []
# 하우상좌
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for _ in range(n):
    array.append(list(map(int,input().split())))

def rotate(array):
    visited = [[False]*m for _ in range(n)]

    for i in range(min(n,m)//2):
        x,y = i,i
        idx = 0
        value = array[x][y]
        array[x][y] = 0

        while True:
            nx,ny = x+dx[idx],y+dy[idx]

            # nx, ny가 배열 안에 있는 수일 때
            if nx >=0 and ny >=0 and nx < n and ny < m:
                # 한바퀴 다 돌면
                if array[nx][ny] == 0:
                    array[nx][ny] = value
                    visited[nx][ny] = True
                    break
                # 방문하지 않은 좌표면
                elif not visited[nx][ny]:
                    # 스왑
                    tmp = array[nx][ny]
                    array[nx][ny] = value
                    value = tmp
                    
                    # 방문 처리, x값 y값 갱신
                    visited[nx][ny] = True
                    x,y = nx,ny
                # 방향을 바꿔야 하면
                else:
                    idx += 1
                    if idx >=4:
                        idx -= 4                 
            else:
                idx += 1
                if idx >=4:
                    idx -= 4

    return array

for _ in range(r):
    rotate(array)

for i in array:
    print(*i)

 

두번째 풀이

왼쪽 면 -> 아래

아래 면 -> 오른쪽

오른쪽 면 -> 위

윗 면 -> 왼쪽

 

다음과 같이 범위를 나누어서 움직여 주기로 했다.

import sys
input = sys.stdin.readline
n,m,r = map(int,input().split())
array = []

for _ in range(n):
    array.append(list(map(int,input().split())))

def rotate(array):
    for i in range(min(n,m)//2):
        x,y = i,i
        # 맨 처음 값 저장
        value = array[x][y]

        # 왼쪽
        for j in range(i+1,n-i):
            x = j
            tmp = array[x][y]
            array[x][y] = value
            value = tmp

        # 아래쪽
        for j in range(i+1, m-i): 
            y = j
            tmp = array[x][y]
            array[x][y] = value
            value = tmp

        # 오른쪽
        for j in range(i+1, n-i): 
            x = n - j - 1 
            tmp = array[x][y] 
            array[x][y] = value
            value = tmp

        # 위
        for j in range(i+1, m-i):
            y = m - j - 1
            tmp = array[x][y]
            array[x][y] = value
            value = tmp
    return array

for _ in range(r):
    rotate(array)

for i in array:
    print(*i)

 

해당 풀이도 시간 초과가 났다.

고민해봐도 아이디어가 생각이 안나서 구글링을 해보았는데 이와 같이 푼 사람들의 코드 전부를 돌려보아도 시간초과 문제가 생겼다.

-> pypy3으로 제출하여 해결!

 

16926번: 배열 돌리기 1