이번 글에서는 양의 정수로 이루어진 배열 arr[]가 주어졌을 때, arr[i]의 값이 인덱스 i와 일치하도록 배열을 재정렬하는 방법을 알아보겠습니다. 단, 배열의 모든 요소는 0보다 크거나 같고 배열의 크기보다 작은 값이어야 합니다. 만약 값 i가 배열에 존재하지 않는다면, 해당 위치에는 -1을 저장하고 최종 결과를 출력합니다.
입출력 예시 시나리오
입력 − int arr[] = {0, 8, 1, 5, 4, 3, 2, 9}
출력 − arr[i] = i 조건에 맞게 재정렬한 결과: 0 1 2 3 4 5 -1 -1
설명 − 크기가 8인 정수 배열이 주어졌고, 모든 요소는 8보다 작은 값을 가집니다. 이제 각 위치를 다음과 같이 재정렬합니다.
arr[0] = 0 (배열에 존재함) arr[1] = 1 (배열에 존재함) arr[2] = 2 (배열에 존재함) arr[3] = 3 (배열에 존재함) arr[4] = 4 (배열에 존재함) arr[5] = 5 (배열에 존재함) arr[6] = -1 (배열에 존재하지 않음) arr[7] = -1 (배열에 존재하지 않음)
입력 − int arr[] = {1, 2, 6, 9, 10}
출력 − arr[i] = i 조건에 맞게 재정렬한 결과: -1 1 2 -1 -1
설명 − 크기가 5인 정수 배열이 주어졌습니다. 이때 값이 배열 범위를 벗어나는 요소(6, 9, 10)는 어느 인덱스와도 일치할 수 없으므로, 해당 자리는 -1로 처리됩니다.
arr[0] = -1 (배열에 존재하지 않음) arr[1] = 1 (배열에 존재함) arr[2] = 2 (배열에 존재함) arr[3] = -1 (배열에 존재하지 않음) arr[4] = -1 (배열에 존재하지 않음)
프로그램에 사용된 접근 방식
정수형 요소로 구성된 배열을 입력받고, 배열의 크기를 계산합니다.
정렬 전 배열을 출력한 뒤, Rearranging(arr, size) 함수를 호출합니다.
Rearranging(arr, size) 함수 내부 동작은 다음과 같습니다.
정수형 변수 ptr을 선언합니다. 이 변수는 스왑(swap) 과정에서 임시로 값을 보관하는 역할을 합니다.
i를 0부터 size 미만까지 반복하는 바깥쪽 FOR 루프를 시작하고, 그 안에서 j를 0부터 size 미만까지 반복하는 안쪽 FOR 루프를 실행합니다.
루프 내에서 arr[j] == i 조건을 확인하고, 참이라면 ptr = arr[j], arr[j] = arr[i], arr[i] = ptr 순서로 두 요소를 교환한 후 break로 안쪽 루프를 종료합니다.
교환이 끝나면, i를 0부터 size 미만까지 반복하며 arr[i] != i인 경우 해당 요소를 -1로 설정합니다.
재정렬이 완료된 배열을 출력합니다.
예제 코드
#include <iostream>
using namespace std;
void Rearranging(int arr[], int size){
int ptr;
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
if(arr[j] == i){
ptr = arr[j];
arr[j] = arr[i];
arr[i] = ptr;
break;
}
}
}
for(int i = 0; i < size; i++){
if(arr[i] != i){
arr[i] = -1;
}
}
}
int main(){
int arr[] = {0, 8, 1, 5, 4, 3, 2, 9 };
int size = sizeof(arr) / sizeof(arr[0]);
//arr[i] = i가 되도록 배열을 재정렬하는 함수 호출
Rearranging(arr, size);
//배열 출력
cout<<"Rearrangement of an array such that arr[i] = i is: ";
for(int i = 0; i < size; i++){
cout << arr[i] << " ";
}
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Rearrangement of an array such that arr[i] = i is: 0 1 2 3 4 5 -1 -1
동작 원리 정리
이 알고리즘의 핵심은 제자리(in-place) 교환 방식입니다. 인덱스 i마다 배열 전체를 훑어 값이 i인 요소를 찾아, 현재 위치의 요소와 맞바꿉니다. 이렇게 하면 별도의 추가 배열 없이 기존 배열만으로 원하는 배치를 만들 수 있습니다.
다만 위 코드는 이중 루프를 사용하므로 시간 복잡도가 O(n²)입니다. 성능이 중요한 환경에서는 해시 셋(unordered_set)에 배열 값을 미리 담아두고, 각 인덱스에 대해 존재 여부만 확인하는 O(n) 방식으로 개선할 수 있습니다. 또한 주어진 예제에서 값이 배열 크기(size) 이상인 요소(예: 두 번째 예시의 6, 9, 10)는 어느 인덱스와도 매칭되지 않으므로, 최종적으로 자연스럽게 -1 처리된다는 점도 함께 기억해두면 좋습니다.