[구현] 백준 16926 (python)

참고)

deque에 대한 설명 / list와의 차이점 / 시간복잡도에 대한 설명

https://wikidocs.net/104977

008 앞뒤에서 자료를 넣고 빼려면? ― collections.deque

deque는 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형으로, 스택(stack)처럼 써도 되고 큐(queue)처럼 써도 된다. collections.deque 모듈은 de…

wikidocs.net

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

몇 달 전에는 분명 실버 문제였는데 지금보니까 골드로 신분상승을..?(왜지 아니 근데 어렵긴 해서 골드인정)

이 문제는 2차원배열의 겉의 배열만 따와서 회전시키고 그 안에 겹을 또 따와서 회전시키고...

이런 문제였다.

정말 복잡했고 일단 들었던 생각은 회전 하기 전과 후의 좌표값의 연관성을 찾아보자 였다.

하지만 연관성이 결국에는 좌표를 이동하면서 알아봐야하는 것이었고

그냥 겉에 한줄씩 가져와서 일차원 배열에 저장하고, 이 배열의 순서를 바꿔서 다시 새로운 2차원 배열에 넣으면 되지 않을까 했다

이것도 생각보다는 어려운 과정이었다.;;

내 풀이

1) 먼저 겉의 배열을 탐색할 때 방향전환을 위해 [[1, 0], [0, 1], [-1, 0], [0, -1]] 와 같이 좌표가 움직여야할 방향성을 지정해주었다.

그리고 maxX, maxY, spot이라는 변수를 만들었는데 이는 좌표들이 움직일 수 있는 범위를 지정해주기 위함이었다.

- maxX, maxY는 x,y가 각각 최대로 갈 수 있는 정수

- spot은 x,y가 최소로 갈 수 있게 되는 정수

2) 이를 바탕으로 spot이 maxX, maxY 둘 다 보다 작을 때까지 while반복문을 돌린다.

- 'min(N,M) mod 2 = 0' 이라는 제한이 있는데 이는 마지막에 내부가 일자로 남지 않는다는 것을 의미하므로 이에 대한 회전은 생각하지 않아도 되어 편했다.

2-1) while문 내부에는 for문을 통해 겉 배열을 탐색해 1차원 배열에 저장하는 과정과 가공한 배열을 다시 newArray에 넣는 과정을 작성했음

- 또한 R이 겉 배열의 길이보다 큰 경우 한 바퀴를 돌게 되는게 손해이므로 아래와 같은 과정도 추가해주었다.

===> 다른 풀이를 봤더니 while대신 min(N,M)만큼 for문을 돌려줘도 됨

2-2) while문 마지막에는 범위를 좁혀주기 위해 maxX, maxY 는 -1, spot은 +1해준다.

import sys

n, m, k = map(int, input().split())
array = []
for _ in range(n):
    array.append(list(sys.stdin.readline().strip().split()))

newArray = [[0 for _ in range(m)] for _ in range(n)]

maxX, maxY = n - 1, m - 1  # 최대로 넘어갈 수 있는
spot = 0  # 시작하는 부분
directionArray = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 탐색할 때 방향전환

# 기존 k 값 저장
original_k = k

while spot < maxX and spot < maxY:
    outArray = []
    loopLen = 2 * ((maxX - spot + 1) + (maxY - spot + 1))-4  # k%loopLen나머지를 다시 k로
    k = original_k % loopLen
    x, y = spot, spot
    direction = -1
    for _ in range(loopLen):

        outArray.append(array[x][y])

        nx = x + directionArray[direction][0]
        ny = y + directionArray[direction][1]

        if nx < spot or ny < spot or nx > maxX or ny > maxY:
            direction += 1
        x += directionArray[direction][0]
        y += directionArray[direction][1]

    newOutArray = outArray[loopLen - k:] + outArray[:loopLen-k]
    # 가공한 배열을 다시 newArray에 넣기
    i = 0
    direction = -1
    x, y = spot, spot
    for _ in range(loopLen):
        newArray[x][y] = newOutArray[i]
        nx = x + directionArray[direction][0]
        ny = y + directionArray[direction][1]

        if nx < spot or ny < spot or nx > maxX or ny > maxY:
            direction += 1

        x += directionArray[direction][0]
        y += directionArray[direction][1]
        i += 1
    spot += 1
    maxX -= 1
    maxY -= 1

for line in newArray:
    print(" ".join(line))

사실 맞기까지 엄청난 오류를 거쳤는데...

도대체 왜 백준 예시는 다 맞는데 어디서 예외가 발생하는가.... 2시간인가 이것만 보고 있었던 것 같다.

그런데 아래 부분에서 기존 k값을 따로 저장하지 않고 계속

k = k % loopLen을 해준게 문제였다. k는 변하면 안되는데 이렇게 되면 반복문 돌면서 계속 변하게 됨;;

맙소사~ 다음엔 주의해야겠다.