[김태원 알고리즘] 곳감(모래시계)

사용 언어: Python3

문제

풀이

내 풀이

from copy import deepcopy

N = int(input())
board = [[int(x) for x in input().split()] for _ in range(N)]
M = int(input())
cmd = [[int(x) for x in input().split()] for _ in range(M)]

# 행번호, 방향, 회전하는 격자수
# 왼쪽: 0, 오른쪽: 1
def rotate(board, num, dir, cnt):
  tmp = deepcopy(board[num]) # deepcopy!!
  if dir == 1: # 오른쪽
    for i in range(N):
      board[num][(i+cnt)%N] = tmp[i]
  else:
    for i in range(N): # 왼쪽
      board[num][(N-cnt+i)%N] = tmp[i]
     

for x in cmd:
  rotate(board, x[0]-1, x[1], x[2])

# output
ans = 0
for i in range(N):
  if i <= N//2:
    for j in range(i, N-i):
      ans += board[i][j]
  else:
    for j in range(N-i-1, i+1):
      ans += board[i][j]
print(ans)

• 성공!
• 왼쪽 회전 시에 인덱스 변화

    board[num][(N-cnt+i)%N] = tmp[i]
  
    # cnt = 3 일 때 (N=5)
    # 0 -> 2 (5-3+0)
    # 1 -> 3 (5-3+1)
    # 2 -> 4 (5-3+2)
    # 3 -> 0 ((5-3+3) % 5)
    # 4 -> 1 ((5-3+4) % 5)
  

다른 사람 풀이

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
M = int(input())

# 행번호, 방향, 회전하는 격자수
# 왼쪽: 0, 오른쪽: 1
for i in range(M):
  num, dir, cnt = map(int, input().split())
  num -= 1 # 문제에서의 1행이 인덱스 0
  if dir == 0: # 왼쪽
    for _ in range(cnt):
      board[num].append(board[num].pop(0)) # ✅ pop() 활용
  else: # 오른쪽
    for _ in range(cnt):
      board[num].insert(0,board[num].pop()) # ✅ pop() 활용

# output
src, dst = 0, N-1
ans = 0
for i in range(N):
  for j in range(src, dst+1):
    ans += board[i][j]
  if i < N//2: # ✅ 좁히기
    src, dst = src + 1, dst - 1
  else: # ✅ 넓히기
    src, dst = src - 1, dst + 1
print(ans)

• 왼쪽 혹은 오른쪽으로 미는 로직에서 pop()을 활용한 것이 인상적인 풀이이다.
  • 왼쪽으로 밀 때에는 맨 앞에서 pop 하여 맨 마지막에 집어넣는다 -> append(x)
  • 오른쪽으로 밀 때에는 맨 뒤에서 pop 하여 맨 앞에 집어넣는다 -> insert(0,x)
• 모래시계 모양으로 순회할 때 src, dst 변수를 두고, 이를 업데이트 하는 방법을 이용하자!

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기