파이썬으로 n번 뒤집기 후 공의 최종 위치 구하기

n개의 공이 있다고 가정해 보겠습니다. 공들은 처음에 1, 2, 3, 4, ..., n 순서대로 정렬되어 있습니다. 먼저 전체 공의 순서를 역순으로 뒤집으면 n, n-1, n-2, ..., 2, 1이 됩니다. 그다음 다시 뒤집기를 수행하는데, 이번에는 1번 위치부터 n번 위치까지만 뒤집으므로 순서는 n, 1, 2, ..., n-1처럼 바뀝니다.

이러한 뒤집기 과정을 총 n번 반복하되, 매번 뒤집기 시작 위치를 오른쪽으로 한 칸씩 이동시킵니다. 우리의 목표는 모든 뒤집기가 끝난 뒤, 처음에 'index' 위치에 있던 공이 최종적으로 어느 위치에 놓이게 되는지 찾는 것입니다.

예를 들어 입력이 balls = 5, index = 2라고 하면 출력은 4가 됩니다. 공들의 초기 배치는 다음과 같습니다.

1, 2, 3, 4, 5

뒤집기가 진행될 때마다 배열은 아래와 같이 변합니다.

5,4,3,2,1
5,1,2,3,4
5,1,4,3,2
5,1,4,2,3

결국 원래 2번 위치에 있던 공은 마지막에 4번 위치로 이동하게 됩니다.

해결 접근 방법

이 문제는 매 단계마다 배열을 일일이 시뮬레이션하지 않아도, 뒤집기 패턴의 규칙성을 활용하면 간단한 수식 하나로 답을 구할 수 있습니다.

만약 index가 balls // 2(balls를 2로 나눈 몫)보다 작다면, 2 * index + 1을 반환합니다.
그렇지 않다면, 2 * (balls - index - 1)을 반환합니다.

동작 원리 살펴보기

뒤집기 과정이 반복될수록 앞쪽 요소들이 하나씩 고정되고, 남은 뒷부분만 계속해서 뒤집히게 됩니다. 이러한 대칭 구조 때문에 배열의 앞쪽 절반에 있던 공과 뒤쪽 절반에 있던 공은 서로 다른 위치 규칙을 따르게 됩니다. 위 수식은 이 특성을 활용하여 반복문 없이도 O(1) 시간 복잡도로 정답을 계산할 수 있습니다.

예시

아래 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(balls, index):
   if index < balls // 2:
      return 2 * index + 1
   else:
      return 2 * (balls - index - 1)

print(solve(5, 2))

입력

5, 2