문제 소개
양의 정수로 구성된 배열 arr[]가 주어집니다. 배열의 크기가 n일 때, 배열의 모든 원소는 0 이상 n 미만의 값을 가집니다. 즉, 모든 원소가 유효한 인덱스 범위 안에 존재한다는 의미입니다. 우리의 과제는 arr[i]의 값이 j라면 arr[j]의 값이 i가 되도록 배열을 재정렬한 뒤, 최종 결과를 출력하는 것입니다.
다르게 표현하면, 이 문제는 주어진 순열의 역순열(inverse permutation)을 구하는 것과 동일합니다. 원래 배열에서 값 v가 위치 i에 있었다면, 새 배열에서는 값 i가 위치 v에 놓이게 됩니다.
입출력 예시
입력 − int arr[] = {3, 4, 1, 2, 0}
출력 −
재정렬 전 배열: 3 4 1 2 0
arr[i]가 j일 때 arr[j]가 i가 되도록 재정렬한 배열: 4 2 3 0 1
설명 − 크기가 5인 정수 배열이 주어졌으며, 모든 원소는 5보다 작은 값을 가집니다. 이제 배열을 재정렬해 보겠습니다.
arr[0]은 3이므로 arr[3] = 0
arr[1]은 4이므로 arr[4] = 1
arr[2]는 1이므로 arr[1] = 2
arr[3]은 2이므로 arr[2] = 3
arr[4]는 0이므로 arr[0] = 4
따라서 최종 배열은 4 2 3 0 1이 됩니다.
입력 − int arr[] = {2, 0, 1, 3}
출력 −
재정렬 전 배열: 2 0 1 3
arr[i]가 j일 때 arr[j]가 i가 되도록 재정렬한 배열: 1 2 0 3
설명 − 크기가 4인 정수 배열이 주어졌으며, 모든 원소는 4보다 작은 값을 가집니다. 이제 배열을 재정렬해 보겠습니다.
arr[0]은 2이므로 arr[2] = 0
arr[1]은 0이므로 arr[0] = 1
arr[2]는 1이므로 arr[1] = 2
arr[3]은 3이므로 arr[3] = 3
따라서 최종 배열은 1 2 0 3이 됩니다.
프로그램에 사용된 접근 방식
정수형 원소로 이루어진 배열을 입력받고 배열의 크기를 계산합니다.
재정렬 전 배열을 출력한 뒤 Rearrangement(arr, size) 함수를 호출합니다.
Rearrangement(arr, size) 함수 내부에서는 다음 작업을 수행합니다.
배열 arr[]와 같은 크기의 정수형 보조 배열 ptr[]을 생성합니다.
i를 0부터 size 미만까지 반복하는 for 루프를 실행하며, 루프 내부에서 ptr[arr[i]]를 i로 설정합니다. 이 단계에서는 '값 v가 위치 i에 있음'이라는 정보를 '위치 v에는 값 i가 와야 함'으로 뒤집어 저장합니다.
다시 i를 0부터 size 미만까지 반복하는 for 루프를 실행하며, 루프 내부에서 arr[i]를 ptr[i]로 설정합니다. 이를 통해 원본 배열이 재정렬된 결과로 덮어씌워집니다.
재정렬이 완료된 배열을 출력합니다.
예제
#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
int ptr[size];
for(int i = 0; i < size; i++){
ptr[arr[i]] = i;
}
for(int i = 0; i < size; i++){
arr[i] = ptr[i];
}
}
int main(){
//배열 입력
int arr[] = {3, 4, 1, 2, 0};
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 such that 'arr[j]' becomes 'i' if 'arr[i]' is 'j' is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Array before Arrangement: 3 4 1 2 0 Rearrangement of an array such that 'arr[j]' becomes 'i' if 'arr[i]' is 'j' is: 4 2 3 0 1
복잡도 분석
시간 복잡도: O(n) — 배열을 두 번 순회하므로 전체 수행 시간은 배열의 크기에 비례합니다.
공간 복잡도: O(n) — 원본 배열과 같은 크기의 보조 배열 ptr[]을 추가로 사용합니다.