백준 17822번 원판 돌리기 (Python)

N개의 원판을 돌리면서 조건에 맞는 번호를 지운 뒤 원판에 적혀있는 숫자의 총합을 구하는 문제입니다.

 

원판은 크기가 작아지는 순서대로 놓여있고, 원판의 중심은 모두 같습니다. 원판의 반지름이 i이면, 그 원판은 i번째 원판이라고 합니다.

각각의 원판에는 M개의 정수가 적혀있고, i 번째 원판에 적힌 j번째 수의 위치를 (i,j)로 표현합니다.

각 위치는 다음을 만족합니다.

• (i, 1)은 (i, 2), (i, M)과 인접하다.
• (i, M)은 (i, M-1), (i, 1)과 인접하다.
• (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
• (1, j)는 (2, j)와 인접하다.
• (N, j)는 (N-1, j)와 인접하다.
• (i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)

 

아래 그림은 N=3, M=4인 경우의 예시입니다.

N=3, M=4인 예시

원판을 회전시키는 경우는 다음과 같습니다.

번호가 xi의 배수인 원판을 di 방향으로 ki칸 회전시킵니다. di가 0인 경우 시계 방향, 1인 경우는 반시계 방향입니다.

원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾습니다.

만약 인접한 수가 있다면, 원판에서 인접하면서 같은 수를 모두 지웁니다.

없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더해줍니다.

 

T번 회전시킨 후 원판에 적힌 수의 합을 구해 출력합니다.

 

 

풀이

0. 변수

plates # 원판 숫자 저장
rotates # 회전 방법
remove # 각 회전 마다 제거할 위치 저장
temp # 인접한 수들의 위치를 저장

 

1. 회전

회전할 크기인 k가 원판에 적힌 숫자의 개수 M보다 항상 작으므로 단순히 K 칸 떨어진 위치에 저장하는 식으로 진행했습니다.

def rotateRight(i, k):
    temp = plates[i][:]
    for j in range(M):
        plates[i][j] = temp[j-k] if j-k >= 0 else temp[M+(j-k)]


def rotateLeft(i, k):
    temp = plates[i][:]
    for j in range(M):
        plates[i][j] = temp[j+k] if j+k < M else temp[j+k-M]

for x, d, k in rotates:
    for i in range(x, N+1, x):
        if d == 0:
            rotateRight(i-1, k)
        else:
            rotateLeft(i-1, k)

오른쪽 회전은 j 인덱스에서 왼쪽으로 k칸 떨어진 숫자를 가져올 수 있도록 했습니다. 만약 j에서 k 칸 왼쪽의 인덱스가 음수라면 M을 더해주어 원형 형태로 이어져 있을 때 k칸 왼쪽의 숫자를 옮겨줄 수 있도록 했습니다.

왼쪽 회전은 j 인덱스에서 으론쪽으로 k칸 떨어진 숫자를 가져올 수 있도록 했습니다. 마찮가지로 j에서 k칸 오른쪽의 인덱스가 M-1보다 크다면 M을 빼주어 원형 형태로 이어져 있을 때 k칸 오른쪽의 숫자를 옮겨줄 수 있도록 했습니다.

 

2. 인접한 숫자 구하기

인접할 조건은 맞닿아 있는 다른 원판 중 같은 위치에 존재하는 숫자일 경우와 같은 원판에서 자신의 좌우에 위치한 숫자일 경우입니다.

이 두 경우를 나누어서 풀이해주었습니다.

 

2.1  맞닿아 있는 다른 원판 중 같은 위치에 존재

맞닿아 있는 원판에서 같은 위치에 동일한 숫자가 있는지 확인해주었습니다.

temp = []
for i in range(M):
    curr = plates[0][i]
    flag = False
    temp.append([0, i])
    for j in range(1, N):
        if curr == plates[j][i]:
            flag = True
            temp.append([j, i])
        else:
            curr = plates[j][i]
            if not flag:
                temp.pop()
            flag = False
            temp.append([j, i])

    if not flag:
        temp.pop()

제거할 숫자가 있다면 temp에 넣어주도록 했습니다.

비교할 숫자를 curr 변수에 넣어주고 반복문을 1부터 시작하여 현재 숫자와 curr을 비교하는 식으로 진행했습니다.

flag 변수는 curr가 이미 동일한 숫자를 마주했는지 알 수 있는 변수입니다.

비교할 숫자들은 모두 temp에 한 번씩은 들어가주도록 했습니다. 다음과 같은 조건으로 temp에 넣은 숫자를 다시 제거할지 확인했습니다.

 

만약 현재 숫자와 curr 숫자가 다르다면 이전에 넣었던 temp를 제거해야되는지 확인합니다.

flag가 True라면 curr이 이미 인접한 숫자 중 같은 숫자가 있다는 뜻이므로 제거하지 않습니다. flag가 False라면 curr이 인접한 숫자가 없다는 뜻이므로 temp에서 제거해줍니다.

만약 현재 숫자와 curr 숫자가 같다면 flag를 True로 바꿔줍니다.

 

마지막으로 넣어준 숫자는 인접한 숫자가 있든 없든 무조건 temp 안에 들어가게 되므로 flag가 False라면 다시 제거해주도록 합니다.

 

2.2 같은 원판에서 자신의 좌우에 위치한 숫자

위의 방식과 비슷하게 풀이를 해주었습니다. 하지만, 이번에는 원형 형태에서 비교를 해야되기 때문에 조금 더 조건을 추가해주었습니다.

temp = []
for i in range(N):
    curr = plates[i][-1]
    temp.append([i, M-1])
    flag = False
    flag2 = False
    for j in range(M):
        if curr == plates[i][j]:
            flag = True
            if j == M-1 and flag2:
                continue
            if j == 0:
                flag2 = True

            temp.append([i, j])
        else:
            curr = plates[i][j]
            if not flag:
                temp.pop()
            flag = False
            temp.append([i, j])

    if not flag:
        temp.pop()

curr, temp, flag는 이전의 방식과 똑같은 기능을 합니다.

flag2는 마지막 숫자가 첫번째 숫자와 동일한 숫자일 경우 True인 조건입니다.

 

만약 curr과 현재 숫자가 같고 j==0이라면 flag2를 True로 바꿔줍니다. 이후 curr과 마지막 숫자가 같고 flag2가 True라면 temp에 이미 마지막 숫자의 위치가 저장되어 있으므로 다시 넣어주지 않도록 해주었습니다.

 

다른 방식은 동일하게 진행해주었습니다.

 

 

이 후 제거할 숫자가 없다면 평균을 비교해서 더해주고 빼는 과정은 반복문으로 구현해주었습니다.

그 다음, 원판의 숫자들의 총합을 출력해주었습니다.

 

 

 

 

 

 

 

해결

오늘도 시간이 너무 오래걸려 힘들었습니다. 글을 쓰면서 리팩토링할 부분이 조금 보여 아쉽기도 한 것 같습니다.

 

백준 17822번 원판돌리기

17822번: 원판 돌리기