이 글에서는 사용자가 입력한 배열과 그룹 크기를 활용해 배열을 뒤집는 방법을 알아봅니다. 핵심 아이디어는 배열을 그룹 크기(p)만큼 잘라 각 부분 배열을 역순으로 뒤집는 것입니다.
만약 그룹 크기(p)가 배열 크기(n)의 배수가 아니라면, 마지막 그룹은 k개 미만의 남은 요소들로 구성되며 이 요소들도 모두 뒤집습니다. 특별한 경우로, p=1이면 배열은 그대로 유지되고, p≥n이면 배열의 모든 요소를 한 번에 뒤집게 됩니다.
알고리즘
Revarray(A, n, p)
/* A는 정수 배열, n은 배열의 크기이며,
배열의 시작부터 크기 p를 가지는 각 부분 배열을 뒤집습니다. */
Step 1: 반복 제어 변수 i를 0으로 초기화합니다.
Step 2: while 반복문으로 i가 n보다 작은지 확인합니다. 참이라면:
Step 2.1: L = i /* 왼쪽 부분 배열 인덱스 */
Step 2.2: R = min(i+p-1, n-1) /* 오른쪽 부분 배열 인덱스 */
Step 2.3: while 반복문으로 L이 R보다 작은지 확인합니다. 참이라면:
Step 2.3.1: 왼쪽 요소 A[L]과 오른쪽 요소 A[R]을 서로 교환(swap)합니다.
Step 2.3.2: L을 1 증가시킵니다.
Step 2.3.3: R을 1 감소시킵니다.
Step 2.4: 내부 while 반복문 종료
Step 2.5: i = i + p
Step 3: 외부 while 반복문 종료
Step 4: 프로그램 종료알고리즘 동작 원리
이 알고리즘은 투 포인터(Two Pointer) 기법을 사용합니다. 각 그룹의 왼쪽 끝 인덱스(L)와 오른쪽 끝 인덱스(R)를 설정한 뒤, 두 포인터가 서로 만날 때까지 양 끝 요소를 교환하며 중앙으로 이동시킵니다. 한 그룹의 뒤집기가 끝나면 i를 p만큼 증가시켜 다음 그룹으로 넘어갑니다. min(i+p-1, n-1)을 사용하기 때문에 마지막 그룹의 크기가 p보다 작아도 배열 범위를 벗어나지 않고 안전하게 처리됩니다.
예제 코드
# 주어진 그룹 크기 단위로 배열을 뒤집는 함수
def arrayreverse(A, n, p):
i = 0
while (i < n):
L = i
R = min(i + p - 1, n - 1)
while (L < R):
A[L], A[R] = A[R], A[L]
L += 1
R -= 1
i += p
# 드라이버 코드
# 배열에 데이터 입력
A = list()
n = int(input("배열의 크기를 입력하세요 :: "))
print("숫자를 입력하세요 ::")
for i in range(int(n)):
k = int(input(""))
A.append(int(k))
p = int(input("그룹의 크기를 입력하세요 :: "))
arrayreverse(A, n, p)
for i in range(0, n):
print(A[i], end=" ")실행 결과
배열의 크기를 입력하세요 :: 6 숫자를 입력하세요 :: 11 22 33 44 55 66 그룹의 크기를 입력하세요 :: 2 22 11 44 33 66 55
결과 분석
위 실행 결과에서 배열 [11, 22, 33, 44, 55, 66]을 그룹 크기 2로 나누면 [11, 22], [33, 44], [55, 66] 세 개의 그룹이 됩니다. 각 그룹을 뒤집으면 [22, 11], [44, 33], [66, 55]가 되어 최종 출력은 22 11 44 33 66 55입니다.
이 알고리즘의 시간 복잡도는 O(n)입니다. 각 요소는 정확히 한 번씩 교환 연산에 참여하기 때문입니다. 공간 복잡도는 추가 배열 없이 제자리(in-place)에서 수행되므로 O(1)입니다.