이번 글에서는 양의 정수로 이루어진 배열 arr[]가 주어졌을 때, 각 원소의 값이 0보다 크거나 같고 배열의 크기보다 작다는 조건 하에, arr[i]가 arr[arr[i]]가 되도록 배열을 재정렬하는 방법을 다룹니다. 단, 추가 공간은 O(1), 즉 상수 크기의 메모리만 사용해야 합니다.
입출력 예시 살펴보기
입력 − int arr[] = {0 3 2 1 5 4}
출력 −
정렬 전 배열: 0 3 2 1 5 4
O(1) 추가 공간으로 arr[i]가 arr[arr[i]]가 되도록 재정렬한 결과: 0 1 2 3 4 5
설명 − 크기가 6인 정수 배열이 주어지고, 모든 원소의 값은 6보다 작습니다. 이제 배열을 재정렬하면 arr[arr[0]]은 0, arr[arr[1]]은 1, arr[arr[2]]는 2, arr[arr[3]]은 3, arr[arr[4]]는 4, arr[arr[5]]는 5가 됩니다. 따라서 최종 결과 배열은 0 1 2 3 4 5입니다.
입력 − int arr[] = {1, 0}
출력 −
정렬 전 배열: 1 0
O(1) 추가 공간으로 arr[i]가 arr[arr[i]]가 되도록 재정렬한 결과: 0 1
설명 − 크기가 2인 정수 배열이 주어지고, 모든 원소의 값은 2보다 작습니다. 재정렬하면 arr[arr[0]]은 1, arr[arr[1]]은 0이 되므로 최종 결과 배열은 0 1입니다.
입력 − int arr[] = {1, 0, 2, 3}
출력 −
정렬 전 배열: 1 0 2 3
O(1) 추가 공간으로 arr[i]가 arr[arr[i]]가 되도록 재정렬한 결과: 0 1 2 3
설명 − 크기가 4인 정수 배열이 주어지고, 모든 원소의 값은 4보다 작습니다. 재정렬하면 arr[arr[0]]은 0, arr[arr[1]]은 1, arr[arr[2]]는 2, arr[arr[3]]은 3이 되므로 최종 결과 배열은 0 1 2 3입니다.
핵심 아이디어: 나눗셈과 나머지 연산 활용
추가 배열 없이 제자리(in-place)에서 재정렬하려면 배열의 각 원소에 두 가지 정보를 동시에 저장하는 기법을 사용합니다. 배열의 크기를 n이라 할 때, 아래 성질을 이용합니다.
- 원래 값 old와 새로 넣을 값 new를 하나의 숫자로 인코딩:
arr[i] = old + new * n - 인코딩된 값에서 원래 값 추출:
arr[i] % n - 인코딩된 값에서 새 값 추출:
arr[i] / n
이렇게 하면 별도의 임시 배열 없이도 모든 원소의 원래 값을 보존하면서 새로운 값을 계산할 수 있습니다.
프로그램에서 사용되는 접근 방식
정수형 배열을 입력받고 배열의 크기를 계산합니다.
재정렬 전 배열을 출력한 뒤, 함수 Rearrangement(arr, size)를 호출합니다.
Rearrangement(arr, size) 함수 내부에서:
i가 0부터 size 미만까지 반복하는 루프를 실행합니다. 루프 안에서 temp를
arr[arr[i]] % size로 설정하고,arr[i] += temp * size를 수행합니다. 이때% size연산으로 아직 변경되지 않은 원래 값을 얻을 수 있습니다.i가 0부터 size 미만까지 반복하는 두 번째 루프를 실행합니다. 루프 안에서
arr[i] = arr[i] / size로 각 원소를 갱신하여 최종 값을 추출합니다.
결과를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
for(int i=0; i < size; i++){
int temp = arr[arr[i]] % size;
arr[i] += temp * size;
}
for(int i = 0; i < size; i++){
arr[i] = arr[i] / size;
}
}
int main(){
//배열 입력
int arr[] = {0, 3, 2, 1, 5, 4};
int size = sizeof(arr) / sizeof(arr[0]);
//원본 배열 출력
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
//배열 재정렬 함수 호출
Rearrangement(arr, size);
//재정렬 후 배열 출력
cout<<"\nRearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Array before Arrangement: 0 3 2 1 5 4 Rearrangement of an array so that arr[i] becomes arr[arr[i]] with O(1) extra space is: 0 1 2 3 4 5
복잡도 분석
시간 복잡도: O(n) — 배열을 두 번 순회하므로 선형 시간이 소요됩니다.
공간 복잡도: O(1) — 추가 배열 없이 몇 개의 변수만 사용하므로 상수 공간입니다.
이처럼 나눗셈과 나머지 연산을 조합하면 추가 메모리 없이도 배열을 효율적으로 재정렬할 수 있습니다. 단, 이 기법은 원소 값이 배열 크기보다 작다는 전제 조건이 반드시 충족되어야 한다는 점에 유의하세요.